oj.uz

Submission #595340

# Submission time Handle Problem Language Result Execution time Memory
595340 2022-07-13T16:12:24 Z piOOE Soccer (JOI17_soccer) C++17
100 / 100
 847 ms 203800 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, 63, sizeof(dp)), memset(mind, 63, 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 167 ms 190620 KB Output is correct
2 Correct 70 ms 188340 KB Output is correct
3 Correct 477 ms 197952 KB Output is correct
4 Correct 509 ms 198836 KB Output is correct
5 Correct 160 ms 188620 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 201748 KB Output is correct
2 Correct 467 ms 202444 KB Output is correct
3 Correct 327 ms 198284 KB Output is correct
4 Correct 326 ms 196728 KB Output is correct
5 Correct 350 ms 198164 KB Output is correct
6 Correct 338 ms 200628 KB Output is correct
7 Correct 470 ms 203764 KB Output is correct
8 Correct 424 ms 203728 KB Output is correct
9 Correct 478 ms 203608 KB Output is correct
10 Correct 129 ms 191104 KB Output is correct
11 Correct 473 ms 203776 KB Output is correct
12 Correct 497 ms 203100 KB Output is correct
13 Correct 300 ms 198988 KB Output is correct
14 Correct 477 ms 203772 KB Output is correct
15 Correct 419 ms 200772 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 190620 KB Output is correct
2 Correct 70 ms 188340 KB Output is correct
3 Correct 477 ms 197952 KB Output is correct
4 Correct 509 ms 198836 KB Output is correct
5 Correct 160 ms 188620 KB Output is correct
6 Correct 495 ms 201748 KB Output is correct
7 Correct 467 ms 202444 KB Output is correct
8 Correct 327 ms 198284 KB Output is correct
9 Correct 326 ms 196728 KB Output is correct
10 Correct 350 ms 198164 KB Output is correct
11 Correct 338 ms 200628 KB Output is correct
12 Correct 470 ms 203764 KB Output is correct
13 Correct 424 ms 203728 KB Output is correct
14 Correct 478 ms 203608 KB Output is correct
15 Correct 129 ms 191104 KB Output is correct
16 Correct 473 ms 203776 KB Output is correct
17 Correct 497 ms 203100 KB Output is correct
18 Correct 300 ms 198988 KB Output is correct
19 Correct 477 ms 203772 KB Output is correct
20 Correct 419 ms 200772 KB Output is correct
21 Correct 189 ms 190356 KB Output is correct
22 Correct 725 ms 196784 KB Output is correct
23 Correct 653 ms 195184 KB Output is correct
24 Correct 847 ms 194348 KB Output is correct
25 Correct 735 ms 200212 KB Output is correct
26 Correct 751 ms 196968 KB Output is correct
27 Correct 359 ms 190500 KB Output is correct
28 Correct 458 ms 191088 KB Output is correct
29 Correct 581 ms 194680 KB Output is correct
30 Correct 384 ms 190712 KB Output is correct
31 Correct 613 ms 203800 KB Output is correct
32 Correct 665 ms 202568 KB Output is correct
33 Correct 396 ms 200536 KB Output is correct
34 Correct 674 ms 200140 KB Output is correct
35 Correct 367 ms 190768 KB Output is correct