oj.uz

Submission #679996

# Submission time Handle Problem Language Result Execution time Memory
679996 2023-01-09T18:34:07 Z bashkort Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 40116 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;

int r, c, need;
int dp[K][C][C], fr[K][C][C], H[R][C], V[R][C];

void update_dp(int L) {
    if (L == need - 1) {
        memcpy(dp[L], fr[L], sizeof(dp[L]));
        return;
    }
    memset(dp[L], 0x3f, sizeof(dp[L]));
    for (int cc = 0; cc < c; ++cc) {
        const int idx = (L + 1) * B - 1;
        
        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[L][mid][cc], fr[L][mid][b] + V[idx][b] + dp[L + 1][b][cc])) {
                    opt = b;
                }
            }

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

}

void update_fr(int L) {
    memset(fr[L], 0x3f, sizeof(fr[L]));
    for (int a = 0; a < c; ++a) {
        fr[L][a][a] = 0;
    }
    int lim = B * L;
    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 cc = 0; cc < c; ++cc) {
                for (int a = 0; a < c; ++a) {
                    fr[L][a][cc] += V[i - 1][a];
                }
            }
        }
    }
}

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) / B;
    for (int i = need - 1; i >= 0; --i) {
        update_fr(i);
    }
    for (int i = need - 1; i >= 0; --i) {
        update_dp(i);
    }
}

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

    int L = P / B;

    update_fr(L);

    if (L == need - 1) {
        memcpy(dp[L], fr[L], sizeof(dp[L]));
    } else {
        update_dp(L);
    }
    for (int i = L - 1; i >= 0; --i) {
        update_dp(i);
    }
}

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

    int L = P / B;

    if ((P + 1) % B != 0) {
        update_fr(L);
    }
    for (int i = L; i >= 0; --i) {
        update_dp(i);
    }
}

int escape(int V1, int V2) {
    return dp[0][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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 34516 KB Output is correct
2 Correct 470 ms 34576 KB Output is correct
3 Correct 520 ms 36172 KB Output is correct
4 Correct 184 ms 34516 KB Output is correct
5 Correct 35 ms 34496 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 4 ms 8388 KB Output is correct
8 Correct 4 ms 8404 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 8404 KB Output is correct
3 Correct 5 ms 8404 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 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 4 ms 8404 KB Output is correct
10 Correct 6 ms 8448 KB Output is correct
11 Correct 71 ms 9388 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 146 ms 8932 KB Output is correct
2 Correct 218 ms 8916 KB Output is correct
3 Correct 226 ms 9040 KB Output is correct
4 Correct 208 ms 8916 KB Output is correct
5 Correct 245 ms 8916 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 4 ms 8404 KB Output is correct
8 Correct 4 ms 8416 KB Output is correct
9 Correct 1056 ms 8924 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 462 ms 38484 KB Output is correct
2 Correct 46 ms 38484 KB Output is correct
3 Correct 186 ms 38408 KB Output is correct
4 Correct 70 ms 39244 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8840 KB Output is correct
2 Correct 218 ms 8948 KB Output is correct
3 Correct 222 ms 8916 KB Output is correct
4 Correct 208 ms 8916 KB Output is correct
5 Correct 253 ms 8940 KB Output is correct
6 Correct 439 ms 38488 KB Output is correct
7 Correct 38 ms 38484 KB Output is correct
8 Correct 190 ms 38480 KB Output is correct
9 Correct 84 ms 39260 KB Output is correct
10 Correct 36 ms 34516 KB Output is correct
11 Correct 429 ms 34552 KB Output is correct
12 Correct 520 ms 36112 KB Output is correct
13 Correct 202 ms 34580 KB Output is correct
14 Correct 35 ms 34600 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 5 ms 8424 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 4 ms 8404 KB Output is correct
21 Correct 4 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 7 ms 8404 KB Output is correct
25 Correct 66 ms 9432 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 1046 ms 8936 KB Output is correct
28 Correct 13082 ms 39064 KB Output is correct
29 Correct 2804 ms 33620 KB Output is correct
30 Correct 12930 ms 33588 KB Output is correct
31 Correct 2819 ms 40108 KB Output is correct
32 Correct 5 ms 8404 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8856 KB Output is correct
2 Correct 211 ms 8928 KB Output is correct
3 Correct 234 ms 8928 KB Output is correct
4 Correct 206 ms 8916 KB Output is correct
5 Correct 244 ms 8916 KB Output is correct
6 Correct 493 ms 38528 KB Output is correct
7 Correct 38 ms 38480 KB Output is correct
8 Correct 211 ms 38484 KB Output is correct
9 Correct 74 ms 39184 KB Output is correct
10 Correct 37 ms 34592 KB Output is correct
11 Correct 429 ms 34560 KB Output is correct
12 Correct 542 ms 36112 KB Output is correct
13 Correct 195 ms 34516 KB Output is correct
14 Correct 35 ms 34572 KB Output is correct
15 Correct 877 ms 38480 KB Output is correct
16 Correct 12966 ms 40116 KB Output is correct
17 Correct 5 ms 8404 KB Output is correct
18 Correct 5 ms 8416 KB Output is correct
19 Correct 6 ms 8412 KB Output is correct
20 Correct 5 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 8384 KB Output is correct
25 Correct 5 ms 8404 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 85 ms 9440 KB Output is correct
28 Correct 4 ms 8404 KB Output is correct
29 Correct 1113 ms 8924 KB Output is correct
30 Correct 14089 ms 38728 KB Output is correct
31 Execution timed out 20055 ms 39024 KB Time limit exceeded
32 Halted 0 ms 0 KB -