Submission #2071424


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair<int, int>;
using namespace std;

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int H, W, K, N, sr, sc;
string board[51];
int fr[2501], fc[2501], f[2501], d[2501];

int dc[] = { 1, 0, -1, 0 };
int dr[] = { 0, 1, 0, -1 };
string dir[] = { "R", "D", "L", "U", "-" };

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> H >> W >> K >> sr >> sc;
    sr--;
    sc--;
    rep(i, H) cin >> board[i];
    cin >> N;
    int turn = 0;
    rep(i, N) {
        cin >> fr[i] >> fc[i] >> f[i] >> d[i];
        fr[i]--;
        fc[i]--;
    }

    bitset<2501> used;
    P pos = make_pair(sr, sc);
    string ans = "";
    while (turn < K) {
        bool hit = false;
        queue<P> que;
        que.push(pos);
        string mp[2501];
        mp[pos.first*50+pos.second] = "";
        bitset<2501> visited;
        visited[pos.first*50+pos.second] = true;
        while (que.size()) {
            P p = que.front();
            que.pop();
            rep(i, 4) {
                int nr = p.first + dr[i], nc = p.second + dc[i];
                if (nr < 0 or nr >= H or nc < 0 or nc >= W or board[nr][nc] == '#' or visited[nr*50+nc] == true) continue;
                mp[nr*50+nc] = mp[p.first*50+p.second] + dir[i];
                visited[nr*50+nc] = true;
                que.push(make_pair(nr, nc));
            }
        }
        int dist = 1e8;
        ll best = 0;
        int idx = -1;
        rep(i, N) {
            if (used[i]) continue;
            if (mp[fr[i]*50+fc[i]].size() > 0 and mp[fr[i]*50+fc[i]].size() + turn <= K and dist >= mp[fr[i]*50+fc[i]].size() and (ll)f[i] - (ll)(mp[fr[i]*50+fc[i]].size() + turn)*d[i] > 0LL) {
                if (dist == mp[fr[i]*50+fc[i]].size() and best > (ll)f[i] - (ll)(mp[fr[i]*50+fc[i]].size() + turn)*d[i]) continue; 
                dist = mp[fr[i]*50+fc[i]].size();
                best = (ll)f[i] - (ll)(mp[fr[i]*50+fc[i]].size() + turn)*d[i];
                idx = i;
                hit = true;
            }
        }

        if (!hit) {
            break;
        }

        ans += mp[fr[idx]*50+fc[idx]];
        turn = ans.size();
        pos = P(fr[idx], fc[idx]);
        used[idx]=true;
    }
    int sz = ans.size();
    for (int i = sz; i<K; ++i) {
        ans += "-";
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task B - Food Collector
User dsytk7
Language C++14 (GCC 5.4.1)
Score 17998
Code Size 2613 Byte
Status AC
Exec Time 92 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 1680 / 20000 2446 / 20000 1860 / 20000 1079 / 20000 1921 / 20000 2318 / 20000 1934 / 20000 1478 / 20000 1141 / 20000 2141 / 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 47 ms 384 KB
subtask_01_02.txt AC 92 ms 512 KB
subtask_01_03.txt AC 72 ms 512 KB
subtask_01_04.txt AC 35 ms 512 KB
subtask_01_05.txt AC 58 ms 512 KB
subtask_01_06.txt AC 79 ms 504 KB
subtask_01_07.txt AC 70 ms 512 KB
subtask_01_08.txt AC 49 ms 508 KB
subtask_01_09.txt AC 30 ms 384 KB
subtask_01_10.txt AC 66 ms 504 KB