oj.uz

Submission #197189

# Submission time Handle Problem Language Result Execution time Memory
197189 2020-01-19T16:21:51 Z junseo None (KOI18_watertank) C++17
100 / 100
 1020 ms 91444 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair<int, int> pii;

const int maxn = 1010;

int n, m, k;
int d[maxn * maxn];
vector<pii> adj[maxn * maxn];

int get_idx(int i, int j) {
    if(i == 0 || i == n+1 || j == 0 || j == m+1) return 0;
    return (i - 1) * m + j;
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n+1; ++i) {
        for(int j = 1; j <= m; ++j) {
            int now; cin >> now;
            now = ~now ? now : 1e9 + 7;
            int i1 = get_idx(i - 1, j), i2 = get_idx(i, j);
            adj[i1].pb({i2, now});
            adj[i2].pb({i1, now});
        }
    }
    for(int i = 1; i <= n; ++i) {
         for(int j = 1; j <= m+1; ++j) {
            int now; cin >> now;
            now = ~now ? now : 1e9 + 7;
            int i1 = get_idx(i, j - 1), i2 = get_idx(i, j);
            adj[i1].pb({i2, now});
            adj[i2].pb({i1, now});
        }
    }

    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) d[get_idx(i, j)] = k;
    priority_queue<pair<int, int>> pq;
    d[0] = 0;   pq.push({-0, 0});

    while(!pq.empty()) {
        int wei = -pq.top().first, now = pq.top().second;
        pq.pop();
        if(wei > d[now]) continue;

        for(auto [nxt, nw] : adj[now]) {
            if(max(wei, nw) < d[nxt]) {
                d[nxt] = max(wei, nw);
                pq.push({-d[nxt], nxt});
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) ans += d[get_idx(i, j)];
    cout << ans;
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24284 KB Output is correct
2 Correct 24 ms 24504 KB Output is correct
3 Correct 25 ms 24312 KB Output is correct
4 Correct 25 ms 24312 KB Output is correct
5 Correct 27 ms 24380 KB Output is correct
6 Correct 27 ms 24440 KB Output is correct
7 Correct 28 ms 24312 KB Output is correct
8 Correct 25 ms 24300 KB Output is correct
9 Correct 26 ms 24440 KB Output is correct
10 Correct 25 ms 24312 KB Output is correct
11 Correct 25 ms 24312 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24312 KB Output is correct
2 Correct 25 ms 24356 KB Output is correct
3 Correct 25 ms 24312 KB Output is correct
4 Correct 31 ms 24568 KB Output is correct
5 Correct 26 ms 24312 KB Output is correct
6 Correct 26 ms 24312 KB Output is correct
7 Correct 26 ms 24440 KB Output is correct
8 Correct 25 ms 24312 KB Output is correct
9 Correct 25 ms 24312 KB Output is correct
10 Correct 18 ms 24444 KB Output is correct
11 Correct 25 ms 24340 KB Output is correct
12 Correct 29 ms 24312 KB Output is correct
13 Correct 26 ms 24440 KB Output is correct
14 Correct 24 ms 24312 KB Output is correct
15 Correct 25 ms 24312 KB Output is correct
16 Correct 25 ms 24312 KB Output is correct
17 Correct 26 ms 24568 KB Output is correct
18 Correct 25 ms 24312 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 81136 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Correct 374 ms 72740 KB Output is correct
4 Correct 417 ms 76024 KB Output is correct
5 Correct 26 ms 24312 KB Output is correct
6 Correct 559 ms 80348 KB Output is correct
7 Correct 390 ms 73516 KB Output is correct
8 Correct 523 ms 79472 KB Output is correct
9 Correct 367 ms 71312 KB Output is correct
10 Correct 25 ms 24312 KB Output is correct
11 Correct 529 ms 77716 KB Output is correct
12 Correct 26 ms 24312 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 24440 KB Output is correct
2 Correct 25 ms 24312 KB Output is correct
3 Correct 25 ms 24312 KB Output is correct
4 Correct 25 ms 24312 KB Output is correct
5 Correct 26 ms 24312 KB Output is correct
6 Correct 25 ms 24312 KB Output is correct
7 Correct 26 ms 24440 KB Output is correct
8 Correct 27 ms 24568 KB Output is correct
9 Correct 25 ms 24340 KB Output is correct
10 Correct 26 ms 24480 KB Output is correct
11 Correct 26 ms 24440 KB Output is correct
12 Correct 25 ms 24312 KB Output is correct
13 Correct 25 ms 24440 KB Output is correct
14 Correct 25 ms 24288 KB Output is correct
15 Correct 25 ms 24316 KB Output is correct
16 Correct 27 ms 24452 KB Output is correct
17 Correct 26 ms 24444 KB Output is correct
18 Correct 27 ms 24440 KB Output is correct
19 Correct 25 ms 24312 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24440 KB Output is correct
2 Correct 26 ms 24316 KB Output is correct
3 Correct 25 ms 24312 KB Output is correct
4 Correct 24 ms 24312 KB Output is correct
5 Correct 25 ms 24440 KB Output is correct
6 Correct 434 ms 81128 KB Output is correct
7 Correct 25 ms 24440 KB Output is correct
8 Correct 25 ms 24316 KB Output is correct
9 Correct 384 ms 74744 KB Output is correct
10 Correct 26 ms 24312 KB Output is correct
11 Correct 25 ms 24312 KB Output is correct
12 Correct 433 ms 81272 KB Output is correct
13 Correct 374 ms 72744 KB Output is correct
14 Correct 25 ms 24312 KB Output is correct
15 Correct 401 ms 74288 KB Output is correct
16 Correct 25 ms 24312 KB Output is correct
17 Correct 26 ms 24440 KB Output is correct
18 Correct 25 ms 24340 KB Output is correct
19 Correct 401 ms 75960 KB Output is correct
20 Correct 26 ms 24440 KB Output is correct
21 Correct 1020 ms 91444 KB Output is correct
22 Correct 27 ms 24568 KB Output is correct
23 Correct 25 ms 24312 KB Output is correct
24 Correct 28 ms 24580 KB Output is correct
25 Correct 26 ms 24444 KB Output is correct
26 Correct 27 ms 24440 KB Output is correct
27 Correct 30 ms 24312 KB Output is correct
28 Correct 591 ms 82132 KB Output is correct
29 Correct 539 ms 80180 KB Output is correct
30 Correct 378 ms 73388 KB Output is correct
31 Correct 507 ms 79332 KB Output is correct
32 Correct 426 ms 78608 KB Output is correct
33 Correct 25 ms 24312 KB Output is correct
34 Correct 367 ms 71260 KB Output is correct
35 Correct 26 ms 24440 KB Output is correct
36 Correct 25 ms 24316 KB Output is correct
37 Correct 26 ms 24440 KB Output is correct
38 Correct 525 ms 77780 KB Output is correct
39 Correct 927 ms 89580 KB Output is correct
40 Correct 27 ms 24316 KB Output is correct
41 Correct 28 ms 24600 KB Output is correct
42 Correct 28 ms 24568 KB Output is correct
43 Correct 27 ms 24540 KB Output is correct
44 Correct 404 ms 76636 KB Output is correct
45 Correct 842 ms 81348 KB Output is correct
46 Correct 25 ms 24312 KB Output is correct