oj.uz

Submission #680074

# Submission time Handle Problem Language Result Execution time Memory
680074 2023-01-09T21:06:53 Z bashkort Wombats (IOI13_wombats) C++17
100 / 100
 9524 ms 68780 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 updateDist(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 b = 0; b < c; ++b) {
                for (int a = 0; a < c - 1; ++a) {
                    ckmin(dist[L][a + 1][b], dist[L][a][b] + H[i][a]);
                }
                for (int a = c - 2; a >= 0; --a) {
                    ckmin(dist[L][a][b], dist[L][a + 1][b] + H[i][a]);
                }

                if (i != lim) {
                    for (int a = 0; a < c; ++a) {
                        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) {
        updateDist(i);
    }
}

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

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

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

    updateDist((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:84:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   84 |     sz = 1 << __lg(need) + bool(need & (need - 1));
      |               ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 63244 KB Output is correct
2 Correct 55 ms 63244 KB Output is correct
3 Correct 121 ms 64844 KB Output is correct
4 Correct 72 ms 63180 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 5 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 8468 KB Output is correct
4 Correct 5 ms 8404 KB Output is correct
5 Correct 5 ms 8404 KB Output is correct
6 Correct 4 ms 8448 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 4 ms 8404 KB Output is correct
9 Correct 5 ms 8384 KB Output is correct
10 Correct 4 ms 8404 KB Output is correct
11 Correct 65 ms 9404 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 168 ms 9172 KB Output is correct
2 Correct 300 ms 9180 KB Output is correct
3 Correct 312 ms 9172 KB Output is correct
4 Correct 295 ms 9164 KB Output is correct
5 Correct 343 ms 9172 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 4 ms 8404 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 1725 ms 9164 KB Output is correct
10 Correct 5 ms 8412 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 67056 KB Output is correct
2 Correct 55 ms 67232 KB Output is correct
3 Correct 73 ms 67148 KB Output is correct
4 Correct 91 ms 67844 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 9172 KB Output is correct
2 Correct 302 ms 9104 KB Output is correct
3 Correct 310 ms 9164 KB Output is correct
4 Correct 299 ms 9168 KB Output is correct
5 Correct 351 ms 9172 KB Output is correct
6 Correct 64 ms 67100 KB Output is correct
7 Correct 58 ms 67156 KB Output is correct
8 Correct 75 ms 67164 KB Output is correct
9 Correct 89 ms 67916 KB Output is correct
10 Correct 52 ms 63156 KB Output is correct
11 Correct 56 ms 63156 KB Output is correct
12 Correct 118 ms 64776 KB Output is correct
13 Correct 76 ms 63248 KB Output is correct
14 Correct 53 ms 63188 KB Output is correct
15 Correct 4 ms 8448 KB Output is correct
16 Correct 4 ms 8404 KB Output is correct
17 Correct 5 ms 8404 KB Output is correct
18 Correct 4 ms 8404 KB Output is correct
19 Correct 6 ms 8480 KB Output is correct
20 Correct 4 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 4 ms 8404 KB Output is correct
25 Correct 67 ms 9416 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 1713 ms 9172 KB Output is correct
28 Correct 2225 ms 67752 KB Output is correct
29 Correct 2205 ms 44216 KB Output is correct
30 Correct 2047 ms 44076 KB Output is correct
31 Correct 2231 ms 68680 KB Output is correct
32 Correct 4 ms 8404 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 9108 KB Output is correct
2 Correct 301 ms 9172 KB Output is correct
3 Correct 316 ms 9172 KB Output is correct
4 Correct 291 ms 9176 KB Output is correct
5 Correct 366 ms 9172 KB Output is correct
6 Correct 59 ms 67032 KB Output is correct
7 Correct 57 ms 67096 KB Output is correct
8 Correct 73 ms 67148 KB Output is correct
9 Correct 93 ms 67868 KB Output is correct
10 Correct 53 ms 63180 KB Output is correct
11 Correct 58 ms 63244 KB Output is correct
12 Correct 124 ms 64888 KB Output is correct
13 Correct 69 ms 63180 KB Output is correct
14 Correct 54 ms 63240 KB Output is correct
15 Correct 819 ms 67204 KB Output is correct
16 Correct 8461 ms 68780 KB Output is correct
17 Correct 5 ms 8404 KB Output is correct
18 Correct 4 ms 8404 KB Output is correct
19 Correct 5 ms 8404 KB Output is correct
20 Correct 4 ms 8404 KB Output is correct
21 Correct 5 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 8488 KB Output is correct
25 Correct 5 ms 8404 KB Output is correct
26 Correct 5 ms 8404 KB Output is correct
27 Correct 68 ms 9420 KB Output is correct
28 Correct 5 ms 8404 KB Output is correct
29 Correct 1698 ms 9172 KB Output is correct
30 Correct 2214 ms 67664 KB Output is correct
31 Correct 8183 ms 67988 KB Output is correct
32 Correct 8323 ms 67900 KB Output is correct
33 Correct 2158 ms 44236 KB Output is correct
34 Correct 8048 ms 44768 KB Output is correct
35 Correct 2035 ms 44384 KB Output is correct
36 Correct 7374 ms 44624 KB Output is correct
37 Correct 2213 ms 68780 KB Output is correct
38 Correct 9524 ms 68640 KB Output is correct
39 Correct 5 ms 8404 KB Output is correct
40 Correct 8131 ms 44608 KB Output is correct