Submission #3820582
Source Code Expand
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
using namespace std;
#define X 50
#define Y 50
#define K 2500
string s[X];
struct food {
int initial_value;
int dec_rate;
food(int _f, int _d) { initial_value = _f; dec_rate = _d; }
food() { initial_value = 0; dec_rate = 0; }
};
food F[X][Y];
//struct food
char dir[X][Y];
bool visited[X][Y];
string dirs = "UDLR";
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int arr_time[X][Y], score[X][Y];
double dfs(int x, int y, int t, int sum) {
// cout << x << ' ' << y << ' ' << t << ' ' << sum << endl;
visited[x][y] = true;
arr_time[x][y] = t;
score[x][y] = sum;
double res = t == 0 ? 0 : (double)sum/t;
if (t == K) return res;
for (int k = 0; k < 4; k++) {
int x1 = x + dx[k], y1 = y + dy[k];
if (0 <= x1 && x1 < X && 0 <= y1 && y1 < Y && !visited[x1][y1] && s[x1][y1] == '.') {
int val = F[x1][y1].initial_value - F[x1][y1].dec_rate * (t - 1);
double tmp = dfs(x1, y1, t+1, sum + val);
if (res < tmp) {
res = tmp;
dir[x][y] = dirs[k];
}
}
}
// cout << res << endl;
return res;
}
double calc(int x, int y, int t) {
memset(visited, 0, sizeof(visited));
memset(dir, 0, sizeof(dir));
memset(arr_time, 0, sizeof(arr_time));
memset(score, 0, sizeof(score));
return dfs(x, y, t, 0);
}
int main() {
int h, w, k, sx, sy; cin >> h >> w >> k >> sx >> sy;
sx--; sy--;
assert(h == X);
assert(w == Y);
assert(k == K);
for (int i = 0; i < X; i++) cin >> s[i];
int n; cin >> n;
for (int i = 0; i < n; i++) {
int x, y, f, d; cin >> x >> y >> f >> d;
x--; y--;
F[x][y] = food(f, d);
}
int t = 0, x = sx, y = sy, cur_score = 0;
char buf[K+1];
while (t < K) {
calc(x, y, t);
if (dir[x][y] == '\0') {
while (t < k) buf[t++] = '-';
break;
}
while (dir[x][y] != '\0') {
buf[t++] = dir[x][y];
switch (dir[x][y]) {
case 'L': y--; break;
case 'R': y++; break;
case 'U': x--; break;
case 'D': x++; break;
}
cur_score += F[x][y].initial_value - F[x][y].dec_rate * (t - 1);
F[x][y] = {0, 0};
// cout << x << ' ' << y << endl;
}
}
assert (t == K);
buf[K] = '\0';
puts(buf);
cerr << cur_score << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Food Collector |
User |
kozima |
Language |
C++14 (GCC 5.4.1) |
Score |
10691 |
Code Size |
2627 Byte |
Status |
AC |
Exec Time |
3 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 |
1274 / 20000 |
1477 / 20000 |
1006 / 20000 |
506 / 20000 |
1026 / 20000 |
1440 / 20000 |
1005 / 20000 |
944 / 20000 |
627 / 20000 |
1386 / 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 |
AC |
2 ms |
384 KB |
subtask_01_02.txt |
AC |
3 ms |
384 KB |
subtask_01_03.txt |
AC |
2 ms |
384 KB |
subtask_01_04.txt |
AC |
2 ms |
384 KB |
subtask_01_05.txt |
AC |
2 ms |
384 KB |
subtask_01_06.txt |
AC |
3 ms |
384 KB |
subtask_01_07.txt |
AC |
2 ms |
384 KB |
subtask_01_08.txt |
AC |
2 ms |
384 KB |
subtask_01_09.txt |
AC |
2 ms |
384 KB |
subtask_01_10.txt |
AC |
2 ms |
384 KB |