oj.uz

Submission #680001

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

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 == 0) {
        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 * 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][cc][mid], dp[L - 1][cc][b] + V[idx][b] + fr[L][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) {
    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 = 0; i < need; ++i) {
        update_fr(i);
    }
    for (int i = 0; i < need; ++i) {
        update_dp(i);
    }
}

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

    int L = P / B;

    update_fr(L);

    for (int i = L; i < need; ++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 < need; ++i) {
        update_dp(i);
    }
}

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 19880 KB Output is correct
2 Correct 18 ms 19880 KB Output is correct
3 Correct 78 ms 21356 KB Output is correct
4 Correct 39 ms 19796 KB Output is correct
5 Correct 61 ms 19796 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 6 ms 8404 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8404 KB Output is correct
2 Correct 5 ms 8404 KB Output is correct
3 Correct 4 ms 8376 KB Output is correct
4 Correct 4 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 8452 KB Output is correct
9 Correct 4 ms 8404 KB Output is correct
10 Correct 5 ms 8404 KB Output is correct
11 Correct 77 ms 9476 KB Output is correct
12 Correct 7 ms 8404 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 8628 KB Output is correct
2 Correct 260 ms 8640 KB Output is correct
3 Correct 309 ms 8632 KB Output is correct
4 Correct 289 ms 8620 KB Output is correct
5 Correct 297 ms 8636 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 1338 ms 8616 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 25 ms 23788 KB Output is correct
2 Correct 66 ms 23764 KB Output is correct
3 Correct 47 ms 23764 KB Output is correct
4 Correct 92 ms 24504 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 8744 KB Output is correct
2 Correct 252 ms 8616 KB Output is correct
3 Correct 290 ms 8624 KB Output is correct
4 Correct 294 ms 8532 KB Output is correct
5 Correct 316 ms 8616 KB Output is correct
6 Correct 23 ms 23788 KB Output is correct
7 Correct 70 ms 23772 KB Output is correct
8 Correct 46 ms 23764 KB Output is correct
9 Correct 101 ms 24512 KB Output is correct
10 Correct 53 ms 19868 KB Output is correct
11 Correct 19 ms 19884 KB Output is correct
12 Correct 81 ms 21452 KB Output is correct
13 Correct 44 ms 19868 KB Output is correct
14 Correct 66 ms 19872 KB Output is correct
15 Correct 4 ms 8404 KB Output is correct
16 Correct 4 ms 8404 KB Output is correct
17 Correct 4 ms 8404 KB Output is correct
18 Correct 5 ms 8492 KB Output is correct
19 Correct 4 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 8500 KB Output is correct
24 Correct 5 ms 8404 KB Output is correct
25 Correct 64 ms 9416 KB Output is correct
26 Correct 5 ms 8392 KB Output is correct
27 Correct 1278 ms 8596 KB Output is correct
28 Correct 3362 ms 24160 KB Output is correct
29 Correct 7304 ms 21420 KB Output is correct
30 Correct 3822 ms 21432 KB Output is correct
31 Correct 7869 ms 25132 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 360 ms 8628 KB Output is correct
2 Correct 283 ms 8620 KB Output is correct
3 Correct 300 ms 8640 KB Output is correct
4 Correct 311 ms 8620 KB Output is correct
5 Correct 299 ms 8660 KB Output is correct
6 Correct 26 ms 23764 KB Output is correct
7 Correct 62 ms 23772 KB Output is correct
8 Correct 43 ms 23764 KB Output is correct
9 Correct 90 ms 24472 KB Output is correct
10 Correct 51 ms 19860 KB Output is correct
11 Correct 18 ms 19880 KB Output is correct
12 Correct 82 ms 21468 KB Output is correct
13 Correct 54 ms 19776 KB Output is correct
14 Correct 58 ms 19860 KB Output is correct
15 Correct 1018 ms 23768 KB Output is correct
16 Execution timed out 20010 ms 24800 KB Time limit exceeded
17 Halted 0 ms 0 KB -