Submission #2151936
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]) - 100 * 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.15;
for (int i = 0; i <= 10; 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.07;
}
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 << endl;
//cout << "end" << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Food Collector |
User |
E869120 |
Language |
C++14 (GCC 5.4.1) |
Score |
13380 |
Code Size |
3458 Byte |
Status |
TLE |
Exec Time |
10503 ms |
Memory |
512 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 |
0 / 20000 |
2611 / 20000 |
1994 / 20000 |
0 / 20000 |
1971 / 20000 |
2433 / 20000 |
2071 / 20000 |
0 / 20000 |
0 / 20000 |
2300 / 20000 |
Status |
|
|
|
|
|
|
|
|
|
|
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 |
TLE |
10114 ms |
384 KB |
subtask_01_02.txt |
AC |
6387 ms |
384 KB |
subtask_01_03.txt |
AC |
9298 ms |
384 KB |
subtask_01_04.txt |
TLE |
10503 ms |
384 KB |
subtask_01_05.txt |
AC |
9922 ms |
384 KB |
subtask_01_06.txt |
AC |
8319 ms |
384 KB |
subtask_01_07.txt |
AC |
9238 ms |
384 KB |
subtask_01_08.txt |
TLE |
10306 ms |
512 KB |
subtask_01_09.txt |
TLE |
10503 ms |
384 KB |
subtask_01_10.txt |
AC |
8603 ms |
384 KB |