oj.uz

Submission #680058

# Submission time Handle Problem Language Result Execution time Memory
680058 2023-01-09T20:46:07 Z bashkort Wombats (IOI13_wombats) C++17
100 / 100
 13969 ms 39724 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 = 200, 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) {
        function<void(int, int, int, int)> solve = [&](int l, int r, int optl, int optr) {
            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(l, mid, optl, opt), solve(mid + 1, r, opt, optr);
        };
        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 27 ms 26836 KB Output is correct
2 Correct 32 ms 26836 KB Output is correct
3 Correct 92 ms 28472 KB Output is correct
4 Correct 38 ms 26836 KB Output is correct
5 Correct 28 ms 26936 KB Output is correct
6 Correct 5 ms 8916 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 4 ms 8916 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8864 KB Output is correct
2 Correct 5 ms 8916 KB Output is correct
3 Correct 6 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 7 ms 8916 KB Output is correct
8 Correct 6 ms 8980 KB Output is correct
9 Correct 7 ms 8916 KB Output is correct
10 Correct 6 ms 8916 KB Output is correct
11 Correct 69 ms 9868 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 256 ms 9084 KB Output is correct
2 Correct 228 ms 9100 KB Output is correct
3 Correct 249 ms 9088 KB Output is correct
4 Correct 257 ms 9088 KB Output is correct
5 Correct 237 ms 9088 KB Output is correct
6 Correct 5 ms 8916 KB Output is correct
7 Correct 5 ms 8916 KB Output is correct
8 Correct 6 ms 8916 KB Output is correct
9 Correct 1184 ms 9104 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 34 ms 30832 KB Output is correct
2 Correct 31 ms 30736 KB Output is correct
3 Correct 43 ms 30832 KB Output is correct
4 Correct 64 ms 31540 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 9212 KB Output is correct
2 Correct 258 ms 9100 KB Output is correct
3 Correct 272 ms 9088 KB Output is correct
4 Correct 280 ms 9084 KB Output is correct
5 Correct 239 ms 9084 KB Output is correct
6 Correct 33 ms 30808 KB Output is correct
7 Correct 31 ms 30844 KB Output is correct
8 Correct 58 ms 30836 KB Output is correct
9 Correct 70 ms 31672 KB Output is correct
10 Correct 28 ms 26836 KB Output is correct
11 Correct 28 ms 26940 KB Output is correct
12 Correct 89 ms 28528 KB Output is correct
13 Correct 39 ms 26928 KB Output is correct
14 Correct 28 ms 26940 KB Output is correct
15 Correct 5 ms 8916 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 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 6 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 8868 KB Output is correct
25 Correct 64 ms 9924 KB Output is correct
26 Correct 5 ms 8916 KB Output is correct
27 Correct 1163 ms 9096 KB Output is correct
28 Correct 3393 ms 31052 KB Output is correct
29 Correct 3503 ms 29844 KB Output is correct
30 Correct 3183 ms 29764 KB Output is correct
31 Correct 3574 ms 32296 KB Output is correct
32 Correct 6 ms 8916 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 9092 KB Output is correct
2 Correct 221 ms 9044 KB Output is correct
3 Correct 245 ms 9108 KB Output is correct
4 Correct 239 ms 9092 KB Output is correct
5 Correct 234 ms 9092 KB Output is correct
6 Correct 33 ms 30848 KB Output is correct
7 Correct 30 ms 30848 KB Output is correct
8 Correct 41 ms 30832 KB Output is correct
9 Correct 62 ms 31584 KB Output is correct
10 Correct 26 ms 26836 KB Output is correct
11 Correct 29 ms 26944 KB Output is correct
12 Correct 87 ms 28444 KB Output is correct
13 Correct 36 ms 26836 KB Output is correct
14 Correct 27 ms 26836 KB Output is correct
15 Correct 894 ms 30748 KB Output is correct
16 Correct 13064 ms 33096 KB Output is correct
17 Correct 4 ms 8916 KB Output is correct
18 Correct 5 ms 8884 KB Output is correct
19 Correct 5 ms 8880 KB Output is correct
20 Correct 5 ms 8916 KB Output is correct
21 Correct 5 ms 8916 KB Output is correct
22 Correct 5 ms 8892 KB Output is correct
23 Correct 5 ms 8916 KB Output is correct
24 Correct 5 ms 8984 KB Output is correct
25 Correct 5 ms 8916 KB Output is correct
26 Correct 8 ms 8916 KB Output is correct
27 Correct 65 ms 11228 KB Output is correct
28 Correct 5 ms 8888 KB Output is correct
29 Correct 1137 ms 9168 KB Output is correct
30 Correct 3328 ms 33460 KB Output is correct
31 Correct 13160 ms 34220 KB Output is correct
32 Correct 13452 ms 39264 KB Output is correct
33 Correct 3439 ms 33280 KB Output is correct
34 Correct 12978 ms 37200 KB Output is correct
35 Correct 3125 ms 33204 KB Output is correct
36 Correct 11836 ms 37152 KB Output is correct
37 Correct 3596 ms 36656 KB Output is correct
38 Correct 13431 ms 39724 KB Output is correct
39 Correct 5 ms 8916 KB Output is correct
40 Correct 13969 ms 37560 KB Output is correct