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
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 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