Submission #2151968


Source Code Expand

#include <iostream>
#include <queue>
#include <string>
#include <functional>
#include <tuple>
#include <cmath>
#include <algorithm>
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()), ex = get<1>(Q.top()), ey = get<2>(Q.top()), tm = get<1>(dist[ex][ey]);
		res = get<0>(dist[ex][ey]); 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;
			if (get<0>(dist[fx][fy]) == -(1 << 30)) {
				get<0>(dist[fx][fy]) = res;
				if (a[fx][fy] >= 1 && used[fx][fy] == false) get<0>(dist[fx][fy]) += vf[a[fx][fy]] - vd[a[fx][fy]] * ((int)S.size() + tm);
				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, 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;
	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;
	}
	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 18341
Code Size 3480 Byte
Status TLE
Exec Time 10046 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 1906 / 20000 2667 / 20000 2051 / 20000 1119 / 20000 2014 / 20000 2498 / 20000 2125 / 20000 1648 / 20000 0 / 20000 2313 / 20000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
TLE × 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 9254 ms 384 KB
subtask_01_02.txt AC 6973 ms 384 KB
subtask_01_03.txt AC 8410 ms 384 KB
subtask_01_04.txt AC 9892 ms 384 KB
subtask_01_05.txt AC 9038 ms 384 KB
subtask_01_06.txt AC 7814 ms 384 KB
subtask_01_07.txt AC 8977 ms 384 KB
subtask_01_08.txt AC 9237 ms 384 KB
subtask_01_09.txt TLE 10046 ms 384 KB
subtask_01_10.txt AC 8259 ms 384 KB