oj.uz

Submission #680075

# Submission time Handle Problem Language Result Execution time Memory
680075 2023-01-09T21:08:16 Z bashkort Wombats (IOI13_wombats) C++17
100 / 100
 5582 ms 68888 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;

inline bool ckmin(int &a, int b) {
    return (a > b) && (a = b, true);
}

constexpr int B = 70, R = 5000, C = 200, K = (R + B - 1) / B + 1;
constexpr int N = K * 2;

int r, c, need, sz = 1;
int dp[2 * N][C][C], dist[K][C][C], H[R][C], V[R][C], opt[C][C];


void pull(int x) {
    memset(dp[x], 0x3f, sizeof(dp[x]));

    if (dp[x << 1 | 1][0][0] == -1) {
        memcpy(dp[x], dp[x << 1], sizeof(dp[x]));
        return;
    }

    for (int a = 0; a < c; ++a) {
        for (int b = c - 1; b >= 0; --b) {
            int lx = (a == 0 ? 0 : opt[a - 1][b]);
            int rx = (b == c - 1 ? c - 1 : opt[a][b + 1]);

            for (int mid = lx; mid <= rx; ++mid) {
                if (ckmin(dp[x][a][b], dp[x << 1][a][mid] + dp[x << 1 | 1][mid][b])) {
                    opt[a][b] = mid;
                }
            }
        }
    }
}

void update(int L) {
    if (L < 0) {
        return;
    }

    int lim = max(0, B * L - 1);

    if (lim < r) {
        memset(dist[L], 0x3f, sizeof(dist[L]));
        for (int a = 0; a < c; ++a) {
            dist[L][a][a] = 0;
        }
        
        for (int i = min(r, B * (L + 1)) - 1; i >= lim; --i) {
            for (int a = 0; a < c - 1; ++a) {
                for (int b = 0; b < c; ++b) {
                    ckmin(dist[L][a + 1][b], dist[L][a][b] + H[i][a]);
                }
            }
            for (int a = c - 2; a >= 0; --a) {
                for (int b = 0; b < c; ++b) {
                    ckmin(dist[L][a][b], dist[L][a + 1][b] + H[i][a]);
                }
            }

            if (i != lim) {
                for (int a = 0; a < c; ++a) {
                    for (int b = 0; b < c; ++b) {
                        dist[L][a][b] += V[i - 1][a];
                    }
                }
            }
        }

        memcpy(dp[sz + L], dist[L], sizeof(dp[sz + L]));
    } else {
        memset(dp[sz + L], -1, sizeof(dp[sz + L]));
    }

    for (int x = sz + L; x >>= 1;) {
        pull(x);
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R, c = C;
    memcpy(::H, H, sizeof(::H)), memcpy(::V, V, sizeof(::V));

    need = r / B + 1;
    sz = 1 << __lg(need) + bool(need & (need - 1));
    for (int i = 0; i < sz; ++i) {
        update(i);
    }
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;

    update(P / B);
    if ((P + 1) % B == 0 && P / B + 1 < need) {
        update(P / B + 1);
    }
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;

    update((P + 1) / B);
}

int escape(int V1, int V2) {
    return dp[1][V1][V2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:88:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   88 |     sz = 1 << __lg(need) + bool(need & (need - 1));
      |               ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 63180 KB Output is correct
2 Correct 54 ms 63244 KB Output is correct
3 Correct 116 ms 64808 KB Output is correct
4 Correct 86 ms 63180 KB Output is correct
5 Correct 69 ms 63184 KB Output is correct
6 Correct 4 ms 8444 KB Output is correct
7 Correct 4 ms 8404 KB Output is correct
8 Correct 4 ms 8404 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8404 KB Output is correct
2 Correct 4 ms 8404 KB Output is correct
3 Correct 6 ms 8404 KB Output is correct
4 Correct 4 ms 8404 KB Output is correct
5 Correct 5 ms 8404 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 5 ms 8404 KB Output is correct
10 Correct 4 ms 8460 KB Output is correct
11 Correct 70 ms 9548 KB Output is correct
12 Correct 5 ms 8404 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 9172 KB Output is correct
2 Correct 187 ms 9176 KB Output is correct
3 Correct 190 ms 9172 KB Output is correct
4 Correct 176 ms 9164 KB Output is correct
5 Correct 501 ms 9164 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 928 ms 9172 KB Output is correct
10 Correct 5 ms 8404 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 67176 KB Output is correct
2 Correct 66 ms 67072 KB Output is correct
3 Correct 70 ms 67148 KB Output is correct
4 Correct 88 ms 67916 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 9168 KB Output is correct
2 Correct 195 ms 9172 KB Output is correct
3 Correct 224 ms 9044 KB Output is correct
4 Correct 190 ms 9172 KB Output is correct
5 Correct 240 ms 9172 KB Output is correct
6 Correct 58 ms 67148 KB Output is correct
7 Correct 53 ms 67148 KB Output is correct
8 Correct 72 ms 67152 KB Output is correct
9 Correct 92 ms 67932 KB Output is correct
10 Correct 55 ms 63152 KB Output is correct
11 Correct 59 ms 63180 KB Output is correct
12 Correct 118 ms 64796 KB Output is correct
13 Correct 75 ms 63156 KB Output is correct
14 Correct 56 ms 63188 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 4 ms 8404 KB Output is correct
17 Correct 4 ms 8404 KB Output is correct
18 Correct 5 ms 8404 KB Output is correct
19 Correct 4 ms 8404 KB Output is correct
20 Correct 6 ms 8404 KB Output is correct
21 Correct 5 ms 8404 KB Output is correct
22 Correct 5 ms 8404 KB Output is correct
23 Correct 6 ms 8404 KB Output is correct
24 Correct 5 ms 8404 KB Output is correct
25 Correct 67 ms 9448 KB Output is correct
26 Correct 5 ms 8404 KB Output is correct
27 Correct 1027 ms 9204 KB Output is correct
28 Correct 1353 ms 67492 KB Output is correct
29 Correct 1772 ms 44232 KB Output is correct
30 Correct 1459 ms 44004 KB Output is correct
31 Correct 1406 ms 68516 KB Output is correct
32 Correct 5 ms 8404 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 9172 KB Output is correct
2 Correct 189 ms 9172 KB Output is correct
3 Correct 199 ms 9184 KB Output is correct
4 Correct 181 ms 9160 KB Output is correct
5 Correct 228 ms 9112 KB Output is correct
6 Correct 60 ms 67032 KB Output is correct
7 Correct 59 ms 67156 KB Output is correct
8 Correct 76 ms 67144 KB Output is correct
9 Correct 110 ms 67928 KB Output is correct
10 Correct 58 ms 63240 KB Output is correct
11 Correct 76 ms 63160 KB Output is correct
12 Correct 130 ms 64844 KB Output is correct
13 Correct 89 ms 63248 KB Output is correct
14 Correct 66 ms 63240 KB Output is correct
15 Correct 885 ms 67332 KB Output is correct
16 Correct 5582 ms 68888 KB Output is correct
17 Correct 4 ms 8404 KB Output is correct
18 Correct 5 ms 8404 KB Output is correct
19 Correct 4 ms 8404 KB Output is correct
20 Correct 5 ms 8404 KB Output is correct
21 Correct 5 ms 8508 KB Output is correct
22 Correct 6 ms 8404 KB Output is correct
23 Correct 6 ms 8480 KB Output is correct
24 Correct 5 ms 8464 KB Output is correct
25 Correct 5 ms 8392 KB Output is correct
26 Correct 5 ms 8404 KB Output is correct
27 Correct 68 ms 9416 KB Output is correct
28 Correct 5 ms 8412 KB Output is correct
29 Correct 1047 ms 9176 KB Output is correct
30 Correct 1375 ms 67532 KB Output is correct
31 Correct 4533 ms 68140 KB Output is correct
32 Correct 4820 ms 68188 KB Output is correct
33 Correct 1429 ms 44252 KB Output is correct
34 Correct 4931 ms 44784 KB Output is correct
35 Correct 1393 ms 44192 KB Output is correct
36 Correct 4936 ms 44896 KB Output is correct
37 Correct 1378 ms 68576 KB Output is correct
38 Correct 4716 ms 68752 KB Output is correct
39 Correct 5 ms 8404 KB Output is correct
40 Correct 5127 ms 44404 KB Output is correct