oj.uz

Submission #680059

# Submission time Handle Problem Language Result Execution time Memory
680059 2023-01-09T20:50:36 Z bashkort Wombats (IOI13_wombats) C++17
100 / 100
 9694 ms 77480 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 = 50, R = 5000, C = 200, K = (R + B - 1) / B;
constexpr int N = (K + 3) * 4;

int r, c, need, sz = 1;
int dp[N][C][C], fr[K * 2][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 = 2 + 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 60 ms 72012 KB Output is correct
2 Correct 66 ms 72016 KB Output is correct
3 Correct 123 ms 73548 KB Output is correct
4 Correct 90 ms 71976 KB Output is correct
5 Correct 74 ms 72012 KB Output is correct
6 Correct 5 ms 8916 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 5 ms 8916 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 9984 KB Output is correct
2 Correct 146 ms 9940 KB Output is correct
3 Correct 215 ms 10028 KB Output is correct
4 Correct 197 ms 10032 KB Output is correct
5 Correct 197 ms 9940 KB Output is correct
6 Correct 5 ms 8916 KB Output is correct
7 Correct 5 ms 8884 KB Output is correct
8 Correct 5 ms 8916 KB Output is correct
9 Correct 913 ms 10024 KB Output is correct
10 Correct 5 ms 8916 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 75916 KB Output is correct
2 Correct 64 ms 75924 KB Output is correct
3 Correct 85 ms 75852 KB Output is correct
4 Correct 107 ms 76608 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 10036 KB Output is correct
2 Correct 153 ms 10024 KB Output is correct
3 Correct 207 ms 9944 KB Output is correct
4 Correct 204 ms 10028 KB Output is correct
5 Correct 200 ms 10044 KB Output is correct
6 Correct 66 ms 75852 KB Output is correct
7 Correct 78 ms 75836 KB Output is correct
8 Correct 89 ms 75924 KB Output is correct
9 Correct 121 ms 76632 KB Output is correct
10 Correct 65 ms 72020 KB Output is correct
11 Correct 67 ms 71992 KB Output is correct
12 Correct 128 ms 73540 KB Output is correct
13 Correct 82 ms 72016 KB Output is correct
14 Correct 66 ms 71984 KB Output is correct
15 Correct 5 ms 8880 KB Output is correct
16 Correct 5 ms 8916 KB Output is correct
17 Correct 5 ms 8916 KB Output is correct
18 Correct 5 ms 8968 KB Output is correct
19 Correct 6 ms 8940 KB Output is correct
20 Correct 5 ms 8976 KB Output is correct
21 Correct 5 ms 8916 KB Output is correct
22 Correct 5 ms 8916 KB Output is correct
23 Correct 5 ms 8916 KB Output is correct
24 Correct 5 ms 8860 KB Output is correct
25 Correct 77 ms 9904 KB Output is correct
26 Correct 5 ms 8916 KB Output is correct
27 Correct 906 ms 10032 KB Output is correct
28 Correct 2075 ms 76236 KB Output is correct
29 Correct 2205 ms 74904 KB Output is correct
30 Correct 2133 ms 74852 KB Output is correct
31 Correct 2535 ms 77308 KB Output is correct
32 Correct 4 ms 8916 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 10040 KB Output is correct
2 Correct 175 ms 10024 KB Output is correct
3 Correct 215 ms 10020 KB Output is correct
4 Correct 205 ms 10036 KB Output is correct
5 Correct 221 ms 10024 KB Output is correct
6 Correct 84 ms 75856 KB Output is correct
7 Correct 70 ms 75856 KB Output is correct
8 Correct 87 ms 75924 KB Output is correct
9 Correct 141 ms 76676 KB Output is correct
10 Correct 64 ms 72016 KB Output is correct
11 Correct 64 ms 72024 KB Output is correct
12 Correct 133 ms 73500 KB Output is correct
13 Correct 94 ms 71908 KB Output is correct
14 Correct 81 ms 71896 KB Output is correct
15 Correct 1954 ms 75888 KB Output is correct
16 Correct 9639 ms 77456 KB Output is correct
17 Correct 5 ms 8916 KB Output is correct
18 Correct 4 ms 8916 KB Output is correct
19 Correct 5 ms 8916 KB Output is correct
20 Correct 5 ms 8916 KB Output is correct
21 Correct 8 ms 8916 KB Output is correct
22 Correct 5 ms 8916 KB Output is correct
23 Correct 5 ms 8884 KB Output is correct
24 Correct 5 ms 8916 KB Output is correct
25 Correct 4 ms 8916 KB Output is correct
26 Correct 5 ms 8932 KB Output is correct
27 Correct 76 ms 9948 KB Output is correct
28 Correct 5 ms 8916 KB Output is correct
29 Correct 936 ms 10032 KB Output is correct
30 Correct 2137 ms 76468 KB Output is correct
31 Correct 8857 ms 76568 KB Output is correct
32 Correct 9176 ms 76688 KB Output is correct
33 Correct 2158 ms 74884 KB Output is correct
34 Correct 8740 ms 75464 KB Output is correct
35 Correct 2044 ms 74896 KB Output is correct
36 Correct 7991 ms 75520 KB Output is correct
37 Correct 2375 ms 77480 KB Output is correct
38 Correct 8915 ms 77296 KB Output is correct
39 Correct 5 ms 8916 KB Output is correct
40 Correct 9694 ms 75200 KB Output is correct