oj.uz

Submission #680057

# Submission time Handle Problem Language Result Execution time Memory
680057 2023-01-09T20:44:47 Z bashkort Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 34756 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 - 1);
    update_fr(L);
    update_fr(L + 1);
}

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

    int L = (P + 1) / B;

    update_fr(L - 1);
    update_fr(L);
    update_fr(L + 1);
}

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 26924 KB Output is correct
2 Correct 65 ms 26924 KB Output is correct
3 Correct 129 ms 28468 KB Output is correct
4 Correct 78 ms 26920 KB Output is correct
5 Correct 53 ms 26832 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 6 ms 8932 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 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 73 ms 9948 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 298 ms 9080 KB Output is correct
2 Correct 235 ms 9164 KB Output is correct
3 Correct 245 ms 9084 KB Output is correct
4 Correct 258 ms 9088 KB Output is correct
5 Correct 249 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 4 ms 8912 KB Output is correct
9 Correct 1231 ms 9100 KB Output is correct
10 Correct 5 ms 8880 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 30840 KB Output is correct
2 Correct 78 ms 30892 KB Output is correct
3 Correct 110 ms 30896 KB Output is correct
4 Correct 107 ms 32224 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 9088 KB Output is correct
2 Correct 228 ms 9084 KB Output is correct
3 Correct 242 ms 9044 KB Output is correct
4 Correct 245 ms 9084 KB Output is correct
5 Correct 234 ms 9084 KB Output is correct
6 Correct 67 ms 30840 KB Output is correct
7 Correct 58 ms 30884 KB Output is correct
8 Correct 113 ms 30904 KB Output is correct
9 Correct 101 ms 32192 KB Output is correct
10 Correct 52 ms 26944 KB Output is correct
11 Correct 60 ms 26956 KB Output is correct
12 Correct 124 ms 29644 KB Output is correct
13 Correct 120 ms 26964 KB Output is correct
14 Correct 74 ms 26828 KB Output is correct
15 Correct 5 ms 8888 KB Output is correct
16 Correct 6 ms 8916 KB Output is correct
17 Correct 5 ms 8888 KB Output is correct
18 Correct 5 ms 8888 KB Output is correct
19 Correct 5 ms 8916 KB Output is correct
20 Correct 5 ms 8916 KB Output is correct
21 Correct 5 ms 8892 KB Output is correct
22 Correct 6 ms 8888 KB Output is correct
23 Correct 6 ms 9020 KB Output is correct
24 Correct 5 ms 8896 KB Output is correct
25 Correct 75 ms 11296 KB Output is correct
26 Correct 5 ms 8916 KB Output is correct
27 Correct 1212 ms 9160 KB Output is correct
28 Correct 9235 ms 33600 KB Output is correct
29 Correct 9324 ms 32244 KB Output is correct
30 Correct 9159 ms 32196 KB Output is correct
31 Correct 9695 ms 34608 KB Output is correct
32 Correct 5 ms 8916 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 9088 KB Output is correct
2 Correct 243 ms 9088 KB Output is correct
3 Correct 247 ms 9044 KB Output is correct
4 Correct 247 ms 9088 KB Output is correct
5 Correct 289 ms 9084 KB Output is correct
6 Correct 66 ms 30804 KB Output is correct
7 Correct 70 ms 30912 KB Output is correct
8 Correct 104 ms 30904 KB Output is correct
9 Correct 102 ms 32280 KB Output is correct
10 Correct 53 ms 26836 KB Output is correct
11 Correct 62 ms 26972 KB Output is correct
12 Correct 147 ms 29692 KB Output is correct
13 Correct 83 ms 26964 KB Output is correct
14 Correct 52 ms 26892 KB Output is correct
15 Correct 1006 ms 33272 KB Output is correct
16 Execution timed out 20016 ms 34756 KB Time limit exceeded
17 Halted 0 ms 0 KB -