oj.uz

Submission #595339

# Submission time Handle Problem Language Result Execution time Memory
595339 2022-07-13T16:08:59 Z piOOE Soccer (JOI17_soccer) C++17
100 / 100
 692 ms 203924 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2001;
const ll inf = 0x3f3f3f3f3f3f3f3fll;

ll dp[5][N][N], mind[N][N];

const int dx[5] = {-1, 1, 0, -1, 0};
const int dy[5] = {-1, 0, -1, 0, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(dp, 0x3f, sizeof(dp)), memset(mind, 0x3f, sizeof(mind));
    ll a, b, c;
    int h, w, n;
    cin >> h >> w >> a >> b >> c >> n;
    vector<int> x(n), y(n);
    queue<pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
        q.push({x[i], y[i]});
        mind[x[i]][y[i]] = 0;
    }
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        for (int k = 1; k <= 4; ++k) {
            int ni = i + dx[k], nj = j + dy[k];
            if (ni >= 0 && ni <= h && nj >= 0 && nj <= w && mind[ni][nj] == inf) {
                mind[ni][nj] = mind[i][j] + c;
                q.push({ni, nj});
            }
        }
    }
    set<tuple<ll, int, int, int>> st;
    auto relax = [&st](ll dist, int tp, int x, int y) {
        if (dp[tp][x][y] > dist) {
            st.erase({dp[tp][x][y], tp, x, y});
            dp[tp][x][y] = dist;
            st.insert({dp[tp][x][y], tp, x, y});
        }
    };
    relax(0, 0, x[0], y[0]);
    while (!st.empty()) {
        auto [d, t, i, j] = *st.begin();
        st.erase(st.begin());
        if (t == 0) {
            for (int k = 1; k <= 4; ++k) {
                int ni = i + dx[k], nj = j + dy[k];
                if (ni >= 0 && ni <= h && nj >= 0 && nj <= w) {
                    relax(d + a + b, k, ni, nj);
                    relax(d + c, 0, ni, nj);
                }
            }
        } else {
            relax(d + mind[i][j], 0, i, j);
            int ni = i + dx[t], nj = j + dy[t];
            if (ni >= 0 && ni <= h && nj >= 0 && nj <= w) {
                relax(d + a, t, ni, nj);
            }
        }
    }
    cout << dp[0][x[n - 1]][y[n - 1]];
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 190764 KB Output is correct
2 Correct 72 ms 188332 KB Output is correct
3 Correct 482 ms 197716 KB Output is correct
4 Correct 507 ms 198780 KB Output is correct
5 Correct 158 ms 188616 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 201748 KB Output is correct
2 Correct 469 ms 202360 KB Output is correct
3 Correct 325 ms 198216 KB Output is correct
4 Correct 350 ms 196724 KB Output is correct
5 Correct 347 ms 198232 KB Output is correct
6 Correct 329 ms 200524 KB Output is correct
7 Correct 488 ms 203884 KB Output is correct
8 Correct 498 ms 203732 KB Output is correct
9 Correct 493 ms 203436 KB Output is correct
10 Correct 130 ms 191204 KB Output is correct
11 Correct 476 ms 203692 KB Output is correct
12 Correct 473 ms 203176 KB Output is correct
13 Correct 285 ms 199024 KB Output is correct
14 Correct 474 ms 203924 KB Output is correct
15 Correct 414 ms 200700 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 190764 KB Output is correct
2 Correct 72 ms 188332 KB Output is correct
3 Correct 482 ms 197716 KB Output is correct
4 Correct 507 ms 198780 KB Output is correct
5 Correct 158 ms 188616 KB Output is correct
6 Correct 494 ms 201748 KB Output is correct
7 Correct 469 ms 202360 KB Output is correct
8 Correct 325 ms 198216 KB Output is correct
9 Correct 350 ms 196724 KB Output is correct
10 Correct 347 ms 198232 KB Output is correct
11 Correct 329 ms 200524 KB Output is correct
12 Correct 488 ms 203884 KB Output is correct
13 Correct 498 ms 203732 KB Output is correct
14 Correct 493 ms 203436 KB Output is correct
15 Correct 130 ms 191204 KB Output is correct
16 Correct 476 ms 203692 KB Output is correct
17 Correct 473 ms 203176 KB Output is correct
18 Correct 285 ms 199024 KB Output is correct
19 Correct 474 ms 203924 KB Output is correct
20 Correct 414 ms 200700 KB Output is correct
21 Correct 193 ms 190356 KB Output is correct
22 Correct 668 ms 196788 KB Output is correct
23 Correct 618 ms 195184 KB Output is correct
24 Correct 692 ms 194360 KB Output is correct
25 Correct 575 ms 200348 KB Output is correct
26 Correct 597 ms 196988 KB Output is correct
27 Correct 363 ms 190420 KB Output is correct
28 Correct 418 ms 191056 KB Output is correct
29 Correct 566 ms 194608 KB Output is correct
30 Correct 368 ms 190796 KB Output is correct
31 Correct 591 ms 203804 KB Output is correct
32 Correct 674 ms 202572 KB Output is correct
33 Correct 379 ms 200632 KB Output is correct
34 Correct 654 ms 200168 KB Output is correct
35 Correct 356 ms 190800 KB Output is correct