oj.uz

Submission #680073

# Submission time Handle Problem Language Result Execution time Memory
680073 2023-01-09T21:04:53 Z bashkort Wombats (IOI13_wombats) C++17
100 / 100
 5170 ms 68992 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], fr[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_fr(int L) {
    if (L < 0) {
        return;
    }

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

    if (lim < r) {
        memset(fr[L], 0x3f, sizeof(fr[L]));
        for (int a = 0; a < c; ++a) {
            fr[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(fr[L][a + 1][b], fr[L][a][b] + H[i][a]);
                }
            }
            for (int a = c - 2; a >= 0; --a) {
                for (int b = 0; b < c; ++b) {
                    ckmin(fr[L][a][b], fr[L][a + 1][b] + H[i][a]);
                }
            }

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

        memcpy(dp[sz + L], fr[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_fr(i);
    }
}

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

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

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

    update_fr((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 51 ms 63244 KB Output is correct
2 Correct 58 ms 63248 KB Output is correct
3 Correct 119 ms 64796 KB Output is correct
4 Correct 71 ms 63188 KB Output is correct
5 Correct 53 ms 63212 KB Output is correct
6 Correct 4 ms 8404 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 5 ms 8404 KB Output is correct
2 Correct 4 ms 8404 KB Output is correct
3 Correct 4 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 8496 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 4 ms 8404 KB Output is correct
10 Correct 5 ms 8404 KB Output is correct
11 Correct 65 ms 9472 KB Output is correct
12 Correct 4 ms 8404 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 9136 KB Output is correct
2 Correct 183 ms 9152 KB Output is correct
3 Correct 199 ms 9160 KB Output is correct
4 Correct 174 ms 9172 KB Output is correct
5 Correct 208 ms 9176 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 4 ms 8404 KB Output is correct
8 Correct 4 ms 8404 KB Output is correct
9 Correct 907 ms 9160 KB Output is correct
10 Correct 4 ms 8404 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 67148 KB Output is correct
2 Correct 56 ms 67148 KB Output is correct
3 Correct 73 ms 67148 KB Output is correct
4 Correct 85 ms 67884 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 9172 KB Output is correct
2 Correct 184 ms 9128 KB Output is correct
3 Correct 191 ms 9172 KB Output is correct
4 Correct 178 ms 9172 KB Output is correct
5 Correct 209 ms 9172 KB Output is correct
6 Correct 62 ms 67152 KB Output is correct
7 Correct 60 ms 67156 KB Output is correct
8 Correct 77 ms 67156 KB Output is correct
9 Correct 86 ms 67860 KB Output is correct
10 Correct 61 ms 63256 KB Output is correct
11 Correct 65 ms 63180 KB Output is correct
12 Correct 114 ms 64776 KB Output is correct
13 Correct 78 ms 63244 KB Output is correct
14 Correct 53 ms 63188 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 4 ms 8440 KB Output is correct
17 Correct 5 ms 8432 KB Output is correct
18 Correct 5 ms 8404 KB Output is correct
19 Correct 5 ms 8404 KB Output is correct
20 Correct 5 ms 8404 KB Output is correct
21 Correct 4 ms 8404 KB Output is correct
22 Correct 4 ms 8404 KB Output is correct
23 Correct 4 ms 8404 KB Output is correct
24 Correct 5 ms 8404 KB Output is correct
25 Correct 64 ms 9380 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 914 ms 9176 KB Output is correct
28 Correct 1268 ms 67652 KB Output is correct
29 Correct 1420 ms 44252 KB Output is correct
30 Correct 1430 ms 44248 KB Output is correct
31 Correct 1377 ms 68776 KB Output is correct
32 Correct 5 ms 8432 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 9172 KB Output is correct
2 Correct 188 ms 9108 KB Output is correct
3 Correct 201 ms 9172 KB Output is correct
4 Correct 197 ms 9172 KB Output is correct
5 Correct 222 ms 9172 KB Output is correct
6 Correct 58 ms 67156 KB Output is correct
7 Correct 56 ms 67080 KB Output is correct
8 Correct 88 ms 67148 KB Output is correct
9 Correct 92 ms 67852 KB Output is correct
10 Correct 59 ms 63220 KB Output is correct
11 Correct 57 ms 63116 KB Output is correct
12 Correct 126 ms 64836 KB Output is correct
13 Correct 77 ms 63220 KB Output is correct
14 Correct 57 ms 63188 KB Output is correct
15 Correct 835 ms 67252 KB Output is correct
16 Correct 5170 ms 68972 KB Output is correct
17 Correct 5 ms 8404 KB Output is correct
18 Correct 4 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 8404 KB Output is correct
22 Correct 5 ms 8404 KB Output is correct
23 Correct 5 ms 8404 KB Output is correct
24 Correct 5 ms 8424 KB Output is correct
25 Correct 5 ms 8404 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 65 ms 9420 KB Output is correct
28 Correct 5 ms 8404 KB Output is correct
29 Correct 901 ms 9180 KB Output is correct
30 Correct 1284 ms 67728 KB Output is correct
31 Correct 4505 ms 68152 KB Output is correct
32 Correct 4608 ms 68100 KB Output is correct
33 Correct 1387 ms 44272 KB Output is correct
34 Correct 4874 ms 44872 KB Output is correct
35 Correct 1391 ms 44132 KB Output is correct
36 Correct 4921 ms 44732 KB Output is correct
37 Correct 1378 ms 68728 KB Output is correct
38 Correct 4783 ms 68992 KB Output is correct
39 Correct 5 ms 8404 KB Output is correct
40 Correct 5170 ms 44740 KB Output is correct