oj.uz

Submission #679960

# Submission time Handle Problem Language Result Execution time Memory
679960 2023-01-09T16:59:25 Z bashkort Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 28660 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;

inline void ckmin(int &a, int b) {
    if (a > b) a = b;
}

constexpr int B = 228, 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 a = 0; a < c; ++a) {
        for (int b = 0; b < c; ++b) {
            for (int cc = 0; cc < c; ++cc) {
                ckmin(dp[L][a][cc], fr[L][a][b] + V[(L + 1) * B - 1][b] + dp[L + 1][b][cc]);
            }
        }
    }
}

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 cc = 0; cc < c; ++cc) {
            for (int a = 0; a < c - 1; ++a) {
                ckmin(fr[L][a + 1][cc], fr[L][a][cc] + H[i][a]);
            }
            for (int a = c - 2; a >= 0; --a) {
                ckmin(fr[L][a][cc], fr[L][a + 1][cc] + H[i][a]);
            }
            if (i != lim) {
                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 20 ms 18900 KB Output is correct
2 Correct 47 ms 18920 KB Output is correct
3 Correct 108 ms 20460 KB Output is correct
4 Correct 43 ms 18900 KB Output is correct
5 Correct 17 ms 18940 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 8356 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8460 KB Output is correct
2 Correct 4 ms 8436 KB Output is correct
3 Correct 4 ms 8404 KB Output is correct
4 Correct 4 ms 8404 KB Output is correct
5 Correct 4 ms 8488 KB Output is correct
6 Correct 5 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 5 ms 8456 KB Output is correct
11 Correct 67 ms 9384 KB Output is correct
12 Correct 5 ms 8404 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 8620 KB Output is correct
2 Correct 416 ms 8620 KB Output is correct
3 Correct 511 ms 8532 KB Output is correct
4 Correct 517 ms 8532 KB Output is correct
5 Correct 518 ms 8620 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 8404 KB Output is correct
9 Correct 2551 ms 8620 KB Output is correct
10 Correct 5 ms 8404 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 22724 KB Output is correct
2 Correct 19 ms 22740 KB Output is correct
3 Correct 38 ms 22740 KB Output is correct
4 Correct 64 ms 23608 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 8620 KB Output is correct
2 Correct 411 ms 8628 KB Output is correct
3 Correct 521 ms 8616 KB Output is correct
4 Correct 517 ms 8652 KB Output is correct
5 Correct 505 ms 8620 KB Output is correct
6 Correct 56 ms 22828 KB Output is correct
7 Correct 23 ms 22844 KB Output is correct
8 Correct 37 ms 22840 KB Output is correct
9 Correct 51 ms 23628 KB Output is correct
10 Correct 17 ms 18832 KB Output is correct
11 Correct 49 ms 18888 KB Output is correct
12 Correct 109 ms 20480 KB Output is correct
13 Correct 34 ms 18900 KB Output is correct
14 Correct 17 ms 18936 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 4 ms 8404 KB Output is correct
17 Correct 5 ms 8404 KB Output is correct
18 Correct 5 ms 8404 KB Output is correct
19 Correct 5 ms 8452 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 5 ms 8404 KB Output is correct
24 Correct 4 ms 8404 KB Output is correct
25 Correct 65 ms 9468 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 2610 ms 8620 KB Output is correct
28 Correct 14362 ms 23332 KB Output is correct
29 Correct 7030 ms 24280 KB Output is correct
30 Correct 11910 ms 24196 KB Output is correct
31 Correct 7257 ms 28660 KB Output is correct
32 Correct 5 ms 8376 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 8744 KB Output is correct
2 Correct 416 ms 8532 KB Output is correct
3 Correct 513 ms 8620 KB Output is correct
4 Correct 516 ms 8620 KB Output is correct
5 Correct 502 ms 8532 KB Output is correct
6 Correct 50 ms 22740 KB Output is correct
7 Correct 20 ms 22740 KB Output is correct
8 Correct 41 ms 22900 KB Output is correct
9 Correct 52 ms 23572 KB Output is correct
10 Correct 17 ms 18940 KB Output is correct
11 Correct 47 ms 18920 KB Output is correct
12 Correct 105 ms 20456 KB Output is correct
13 Correct 34 ms 18900 KB Output is correct
14 Correct 17 ms 18916 KB Output is correct
15 Correct 808 ms 22764 KB Output is correct
16 Execution timed out 20041 ms 24680 KB Time limit exceeded
17 Halted 0 ms 0 KB -