Submission #3823717

---

Source Code Expand

#include <queue>
#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];

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];
bool allow_minus = true;

struct state { char x, y; int sum; };

state 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));
    queue<state> q;
    q.push((state){x, y, 0});
    arr_time[x][y] = t;
    visited[x][y] = true;
    double max_avg = 0.0;
    state best = {-1, -1, 0};
    while (!q.empty()) {
        x = q.front().x, y = q.front().y;
        int sum = q.front().sum;
        q.pop();
        int max_score = 0, max_dir = -1;
        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] == '.' && arr_time[x1][y1] < K) {
                int val = F[x1][y1].initial_value - F[x1][y1].dec_rate * (t - 1);
                if (!allow_minus && val < 0) continue;
                score[x1][y1] = score[x][y] + val;
                arr_time[x1][y1] = arr_time[x][y] + 1;
                visited[x1][y1] = true;
                dir[x1][y1] = dirs[k];
                q.push((state){x1, y1, score[x][y] + val});
                assert (arr_time[x1][y1] > t);
                if (max_avg < (double)score[x1][y1]/(arr_time[x1][y1] - t)) {
                    max_avg = (double)score[x1][y1]/(arr_time[x1][y1] - t);
                    best = (state){x1, y1, score[x1][y1]};
                }
            }
        }
    }
    return best;
}

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) {
        state st = calc(x, y, t);
        if (st.sum == 0) {
            if (allow_minus) {
                allow_minus = false;
                continue;
            } else {
                while (t < K) buf[t++] = '-';
                break;
            }
        }
        // cout << "from " << x << ' ' << y << " to " << (int)st.x << ' ' << (int)st.y << endl;
        for (int x0 = st.x, y0 = st.y, t0 = arr_time[x0][y0]-1; t <= t0; t0--) {
            assert(x0 != x || y0 != y);
            buf[t0] = dir[x0][y0];
            switch (dir[x0][y0]) {
            case 'L': y0++; break;
            case 'R': y0--; break;
            case 'U': x0++; break;
            case 'D': x0--; break;
            default: assert(false);
            }
            F[x0][y0] = {0, 0};
            // cout << t0 << ' ' << x0 << ' ' << y0 << endl;
        }
        //cout << endl;
        x = st.x; y = st.y; t = arr_time[x][y];
        cur_score += st.sum;
    }
    assert (t == K);
    buf[K] = '\0';
    puts(buf);
    cerr << cur_score << endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘state calc(int, int, int)’:
./Main.cpp:34:27: warning: narrowing conversion of ‘x’ from ‘int’ to ‘char’ inside { } [-Wnarrowing]
     q.push((state){x, y, 0});
                           ^
./Main.cpp:34:27: warning: narrowing conversion of ‘y’ from ‘int’ to ‘char’ inside { } [-Wnarrowing]
./Main.cpp:54:57: warning: narrowing conversion of ‘x1’ from ‘int’ to ‘char’ inside { } [-Wnarrowing]
                 q.push((state){x1, y1, score[x][y] + val});
                                                         ^
./Main.cpp:54:57: warning: narrowing conversion of ‘y1’ from ‘int’ to ‘char’ inside { } [-Wnarrowing]
./Main.cpp:58:57: warning: narrowing conversion of ‘x1’ from ‘int’ to ‘char’ inside { } [-Wnarrowing]
                     best = (state){x1, y1, score[x1][y1]};
                                                         ^
./Main.cpp:58:57: warning: narrowing conversion of ‘y1’ from ‘int’ to ‘char’ inside { } [-Wnarrowing]

Judge Result