Submission #2151998


Source Code Expand

#include <iostream>
#include <queue>
#include <string>
#include <functional>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <ctime>
using namespace std;
#pragma warning (disable: 4996)

int H, W, K, N, sx, sy, cx, cy, a[52][52], vx[2509], vy[2509], vf[2509], vd[2509], score; long double M;
bool used[52][52]; tuple<int, int, int, int> dist[52][52];
string S;

void maximize() {
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) dist[i][j] = make_tuple(-(1 << 30), -1, -1, -1);
	}
	dist[cx][cy] = make_tuple(0, 0, -1, -1);
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, less<tuple<int, int, int>>>Q;
	Q.push(make_tuple(0, cx, cy));

	while (!Q.empty()) {
		int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
		int res = get<0>(Q.top()), res2 = res, ex = get<1>(Q.top()), ey = get<2>(Q.top()), tm = get<1>(dist[ex][ey]);
		res = get<0>(dist[ex][ey]); if (tm >= 1) res2 += 4000 * (tm - 1); Q.pop();
		for (int i = 0; i < 4; i++) {
			int fx = ex + dx[i], fy = ey + dy[i];
			if (fx <= 0 || fy <= 0 || fx > H || fy > W || a[fx][fy] == -1) continue;

			long double E = res; int F = 0;
			if (a[fx][fy] >= 1 && used[fx][fy] == false) {
				E += vf[a[fx][fy]] - vd[a[fx][fy]] * ((int)S.size() + tm);
				if (vf[a[fx][fy]] >= 1)F += vd[a[fx][fy]] * 500;
			}

			if (get<0>(dist[fx][fy]) == -(1 << 30) || (get<0>(dist[fx][fy]) < E && get<1>(dist[fx][fy]) > tm + 1)) {
				get<0>(dist[fx][fy]) = E;
				get<1>(dist[fx][fy]) = tm + 1;
				get<2>(dist[fx][fy]) = ex;
				get<3>(dist[fx][fy]) = ey;
				Q.push(make_tuple(get<0>(dist[fx][fy]) - 4000 * tm + F, fx, fy));
			}
		}
	}

	long double maxn = -1; int bx = 0, by = 0;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			long double D = 1.0L*get<0>(dist[i][j]) / powl(1.0L*get<1>(dist[i][j]) + 1, M);
			if (maxn < D) {
				maxn = D; bx = i; by = j;
			}
		}
	}
	if (bx == cx && by == cy) S += "-";
	else {
		int gx = bx, gy = by; string Z = "";
		while (gx != cx || gy != cy) {
			int wx = get<2>(dist[gx][gy]), wy = get<3>(dist[gx][gy]);
			if (gx == wx) {
				if (wy < gy) Z += "R";
				if (wy > gy) Z += "L";
			}
			else {
				if (wx < gx) Z += "D";
				if (wx > gx) Z += "U";
			}
			gx = wx; gy = wy;
		}
		reverse(Z.begin(), Z.end());
		for (int i = 0; i < Z.size(); i++) {
			if (Z[i] == 'L') cy--;
			if (Z[i] == 'R') cy++;
			if (Z[i] == 'U') cx--;
			if (Z[i] == 'D') cx++;
			if (a[cx][cy] >= 1 && used[cx][cy] == false) {
				used[cx][cy] = true;
				score += vf[a[cx][cy]] - vd[a[cx][cy]] * ((int)S.size());
			}
			if (Z.size() == K) break;
			S += Z[i];
		}
	}
}

int main() {
	//FILE *in = freopen("in1.txt", "r", stdin);
	//FILE *out = freopen("out1.txt", "w", stdout);
	cin >> H >> W >> K >> sx >> sy;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			char c; cin >> c;
			if (c == '#') a[i][j] = -1;
		}
	}
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> vx[i] >> vy[i] >> vf[i] >> vd[i];
		a[vx[i]][vy[i]] = i;
	}
	long double maxn = 0; int maxs = 0; M = 0.25; int ti = clock();
	for (int i = 0; i <= 8; i++) {
		for (int j = 1; j <= H; j++) { for (int k = 1; k <= W; k++) used[j][k] = false; }
		cx = sx; cy = sy; S = ""; score = 0;
		while (S.size() < K) {
			maximize();
		}
		if (score > maxs) {
			maxs = score; maxn = M;
		}
		M += 0.13;
		if ((clock() - ti) > 7000000) break;
	}
	for (int j = 1; j <= H; j++) { for (int k = 1; k <= W; k++) used[j][k] = false; }
	cx = sx; cy = sy; M = maxn; S = ""; score = 0;
	while (S.size() < K) {
		maximize();
	}
	cout << S << endl;
	//cout << "#score = " << score << " " << maxn << " " << endl;
	//cout << "end" << endl;
	return 0;
}

Submission Info

Submission Time
Task B - Food Collector
User E869120
Language C++14 (GCC 5.4.1)
Score 19421
Code Size 3758 Byte
Status AC
Exec Time 9057 ms
Memory 384 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 1857 / 20000 2655 / 20000 1999 / 20000 1102 / 20000 1977 / 20000 2561 / 20000 2107 / 20000 1641 / 20000 1188 / 20000 2334 / 20000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 8159 ms 384 KB
subtask_01_02.txt AC 7253 ms 384 KB
subtask_01_03.txt AC 8815 ms 384 KB
subtask_01_04.txt AC 9057 ms 384 KB
subtask_01_05.txt AC 8100 ms 384 KB
subtask_01_06.txt AC 8046 ms 384 KB
subtask_01_07.txt AC 8733 ms 384 KB
subtask_01_08.txt AC 8460 ms 384 KB
subtask_01_09.txt AC 9008 ms 384 KB
subtask_01_10.txt AC 8540 ms 384 KB