oj.uz

Submission #520016

# Submission time Handle Problem Language Result Execution time Memory
520016 2022-01-28T06:18:01 Z Giantpizzahead Soccer (JOI17_soccer) C++17
100 / 100
 415 ms 18596 KB 
/*
Solution: 
Runtime: 
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (true) cerr
using ll = long long;

const int MAXD = 505;
const ll INF = 1e18;

int H, W, N;
int si, sj, ei, ej;
ll A, B, C;
ll costP[MAXD][MAXD];

int ci[] = {1, 0, -1, 0}, cj[] = {0, 1, 0, -1};

inline bool inBounds(int i, int j) {
    return i >= 0 && i < H && j >= 0 && j < W;
}

// 0-3 = Being kicked, 4 = Player has the ball
ll bestC[MAXD][MAXD][5];
struct Loc {
    int i, j, k;
    ll c;
    bool operator<(const Loc& o) const {
        return c > o.c;
    }
};
priority_queue<Loc> pq;

void tryTrans(int i, int j, int k, ll c) {
    if (!inBounds(i, j) || bestC[i][j][k] <= c) return;
    bestC[i][j][k] = c;
    pq.push({i, j, k, c});
}

void bfs1() {
    while (!pq.empty()) {
        Loc l = pq.top(); pq.pop();
        int i = l.i, j = l.j;
        ll c = l.c;
        if (c != costP[i][j]) continue;
        // Move to adjacent square
        rep(d, 0, 4) {
            int ni = i + ci[d], nj = j + cj[d];
            ll nc = c + C;
            if (!inBounds(ni, nj) || costP[ni][nj] <= nc) continue;
            costP[ni][nj] = nc;
            pq.push({ni, nj, -1, nc});
        }
    }
}

void bfs2() {
    bestC[si][sj][4] = 0;
    pq.push({si, sj, 4, 0});
    while (!pq.empty()) {
        Loc l = pq.top(); pq.pop();
        int i = l.i, j = l.j, k = l.k;
        ll c = l.c;
        if (c != bestC[i][j][k]) continue;
        if (k == 4) {
            // Player has the ball
            rep(d, 0, 4) {
                tryTrans(i + ci[d], j + cj[d], 4, c + C);  // Move with the ball
                tryTrans(i, j, d, c + B);  // Kick the ball in a direction
            }
        } else {
            // Ball is being kicked
            // Continue moving the ball
            tryTrans(i + ci[k], j + cj[k], k, c + A);
            // Stop moving and have a player pick up the ball
            tryTrans(i, j, 4, c + costP[i][j]);
        }
    }
}

void solve() {
    cin >> H >> W;
    H++, W++;
    cin >> A >> B >> C;
    cin >> N;
    rep(i, 0, H) rep(j, 0, W) {
        costP[i][j] = INF;
        rep(k, 0, 5) bestC[i][j][k] = INF;
    }
    rep(k, 0, N) {
        int i, j; cin >> i >> j;
        if (k == 0) si = i, sj = j;
        else if (k == N-1) ei = i, ej = j;
        costP[i][j] = 0;
        pq.push({i, j, -1, 0});
    }
    bfs1();
    bfs2();
    ll ans = INF;
    rep(i, 0, H) rep(j, 0, W) rep(k, 0, 5) {
        ll cost = bestC[i][j][k] + C * (abs(ei-i) + abs(ej-j));
        ans = min(cost, ans);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6724 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 280 ms 18488 KB Output is correct
4 Correct 300 ms 18476 KB Output is correct
5 Correct 54 ms 6852 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 18480 KB Output is correct
2 Correct 309 ms 18420 KB Output is correct
3 Correct 238 ms 16052 KB Output is correct
4 Correct 237 ms 18416 KB Output is correct
5 Correct 240 ms 18352 KB Output is correct
6 Correct 261 ms 18396 KB Output is correct
7 Correct 337 ms 18376 KB Output is correct
8 Correct 296 ms 18380 KB Output is correct
9 Correct 334 ms 18480 KB Output is correct
10 Correct 42 ms 7556 KB Output is correct
11 Correct 321 ms 18416 KB Output is correct
12 Correct 329 ms 18596 KB Output is correct
13 Correct 191 ms 16044 KB Output is correct
14 Correct 323 ms 18484 KB Output is correct
15 Correct 244 ms 18456 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6724 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 280 ms 18488 KB Output is correct
4 Correct 300 ms 18476 KB Output is correct
5 Correct 54 ms 6852 KB Output is correct
6 Correct 329 ms 18480 KB Output is correct
7 Correct 309 ms 18420 KB Output is correct
8 Correct 238 ms 16052 KB Output is correct
9 Correct 237 ms 18416 KB Output is correct
10 Correct 240 ms 18352 KB Output is correct
11 Correct 261 ms 18396 KB Output is correct
12 Correct 337 ms 18376 KB Output is correct
13 Correct 296 ms 18380 KB Output is correct
14 Correct 334 ms 18480 KB Output is correct
15 Correct 42 ms 7556 KB Output is correct
16 Correct 321 ms 18416 KB Output is correct
17 Correct 329 ms 18596 KB Output is correct
18 Correct 191 ms 16044 KB Output is correct
19 Correct 323 ms 18484 KB Output is correct
20 Correct 244 ms 18456 KB Output is correct
21 Correct 59 ms 6724 KB Output is correct
22 Correct 368 ms 18408 KB Output is correct
23 Correct 343 ms 14132 KB Output is correct
24 Correct 382 ms 15384 KB Output is correct
25 Correct 334 ms 18488 KB Output is correct
26 Correct 331 ms 18416 KB Output is correct
27 Correct 209 ms 15424 KB Output is correct
28 Correct 182 ms 18496 KB Output is correct
29 Correct 301 ms 15424 KB Output is correct
30 Correct 177 ms 15360 KB Output is correct
31 Correct 342 ms 18460 KB Output is correct
32 Correct 415 ms 18476 KB Output is correct
33 Correct 279 ms 18404 KB Output is correct
34 Correct 396 ms 18476 KB Output is correct
35 Correct 164 ms 15976 KB Output is correct