oj.uz

Submission #680068

# Submission time Handle Problem Language Result Execution time Memory
680068 2023-01-09T20:56:30 Z bashkort Wombats (IOI13_wombats) C++17
100 / 100
 10540 ms 77616 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;
const int N = K * 2;

int r, c, need, sz = 1;
int dp[2 * N][C][C], fr[N][C][C], H[R][C], V[R][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 cc = 0; cc < c; ++cc) {
        auto solve = [&](auto solve, int l, int r, int optl, int optr) -> void {
            if (l >= r) {
                return;
            }

            int mid = (l + r) >> 1;

            int opt = optl;

            for (int b = optl; b <= optr; ++b) {
                if (ckmin(dp[x][cc][mid], dp[x << 1][cc][b] + dp[x << 1 | 1][b][mid])) {
                    opt = b;
                }
            }

            solve(solve, l, mid, optl, opt), solve(solve, mid + 1, r, opt, optr);
        };
        solve(solve, 0, c, 0, c - 1);
    }
}

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

    memcpy(dp[sz + L], fr[L], 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 = 1 + r / B;
    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;

    int L = P / B;

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

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

    int L = (P + 1) / B;

    update_fr(L);
}

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 71884 KB Output is correct
2 Correct 61 ms 71916 KB Output is correct
3 Correct 125 ms 73548 KB Output is correct
4 Correct 78 ms 71944 KB Output is correct
5 Correct 57 ms 71904 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 4 ms 8404 KB Output is correct
8 Correct 5 ms 8360 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 8436 KB Output is correct
3 Correct 5 ms 8404 KB Output is correct
4 Correct 6 ms 8404 KB Output is correct
5 Correct 5 ms 8404 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 8492 KB Output is correct
9 Correct 5 ms 8404 KB Output is correct
10 Correct 7 ms 8436 KB Output is correct
11 Correct 73 ms 9396 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 115 ms 9048 KB Output is correct
2 Correct 188 ms 9084 KB Output is correct
3 Correct 199 ms 9044 KB Output is correct
4 Correct 174 ms 9048 KB Output is correct
5 Correct 201 ms 9084 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 970 ms 9084 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 80 ms 75916 KB Output is correct
2 Correct 72 ms 75912 KB Output is correct
3 Correct 81 ms 75884 KB Output is correct
4 Correct 97 ms 76656 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 9084 KB Output is correct
2 Correct 193 ms 9084 KB Output is correct
3 Correct 185 ms 9092 KB Output is correct
4 Correct 175 ms 9088 KB Output is correct
5 Correct 203 ms 9104 KB Output is correct
6 Correct 67 ms 75920 KB Output is correct
7 Correct 63 ms 75852 KB Output is correct
8 Correct 80 ms 75804 KB Output is correct
9 Correct 97 ms 76620 KB Output is correct
10 Correct 57 ms 71884 KB Output is correct
11 Correct 63 ms 72000 KB Output is correct
12 Correct 126 ms 73548 KB Output is correct
13 Correct 74 ms 72004 KB Output is correct
14 Correct 59 ms 71968 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 7 ms 8404 KB Output is correct
17 Correct 5 ms 8404 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 5 ms 8404 KB Output is correct
22 Correct 5 ms 8404 KB Output is correct
23 Correct 5 ms 8456 KB Output is correct
24 Correct 5 ms 8404 KB Output is correct
25 Correct 71 ms 9376 KB Output is correct
26 Correct 5 ms 8404 KB Output is correct
27 Correct 955 ms 9084 KB Output is correct
28 Correct 2132 ms 76344 KB Output is correct
29 Correct 2181 ms 45072 KB Output is correct
30 Correct 2199 ms 44792 KB Output is correct
31 Correct 2500 ms 77284 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 121 ms 9080 KB Output is correct
2 Correct 190 ms 9088 KB Output is correct
3 Correct 192 ms 9084 KB Output is correct
4 Correct 176 ms 9080 KB Output is correct
5 Correct 217 ms 9164 KB Output is correct
6 Correct 65 ms 75860 KB Output is correct
7 Correct 74 ms 75840 KB Output is correct
8 Correct 75 ms 75808 KB Output is correct
9 Correct 95 ms 76720 KB Output is correct
10 Correct 67 ms 72012 KB Output is correct
11 Correct 60 ms 71884 KB Output is correct
12 Correct 129 ms 73580 KB Output is correct
13 Correct 76 ms 72008 KB Output is correct
14 Correct 57 ms 71988 KB Output is correct
15 Correct 1657 ms 75952 KB Output is correct
16 Correct 9904 ms 77616 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 4 ms 8404 KB Output is correct
23 Correct 5 ms 8404 KB Output is correct
24 Correct 5 ms 8404 KB Output is correct
25 Correct 5 ms 8404 KB Output is correct
26 Correct 5 ms 8480 KB Output is correct
27 Correct 70 ms 9420 KB Output is correct
28 Correct 4 ms 8404 KB Output is correct
29 Correct 961 ms 9088 KB Output is correct
30 Correct 2252 ms 76264 KB Output is correct
31 Correct 8760 ms 76492 KB Output is correct
32 Correct 10540 ms 76544 KB Output is correct
33 Correct 2095 ms 45116 KB Output is correct
34 Correct 8393 ms 45192 KB Output is correct
35 Correct 2139 ms 44820 KB Output is correct
36 Correct 8328 ms 45168 KB Output is correct
37 Correct 2461 ms 77356 KB Output is correct
38 Correct 9318 ms 77204 KB Output is correct
39 Correct 4 ms 8404 KB Output is correct
40 Correct 9066 ms 45116 KB Output is correct