oj.uz

Submission #679965

# Submission time Handle Problem Language Result Execution time Memory
679965 2023-01-09T17:05:13 Z bashkort Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 22136 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 = 350, 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 16 ms 16724 KB Output is correct
2 Correct 46 ms 16724 KB Output is correct
3 Correct 95 ms 18316 KB Output is correct
4 Correct 27 ms 16724 KB Output is correct
5 Correct 21 ms 16636 KB Output is correct
6 Correct 5 ms 8428 KB Output is correct
7 Correct 7 ms 8404 KB Output is correct
8 Correct 5 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 8404 KB Output is correct
4 Correct 5 ms 8404 KB Output is correct
5 Correct 4 ms 8404 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 5 ms 8404 KB Output is correct
10 Correct 5 ms 8468 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 521 ms 8616 KB Output is correct
2 Correct 427 ms 8632 KB Output is correct
3 Correct 524 ms 8612 KB Output is correct
4 Correct 548 ms 8616 KB Output is correct
5 Correct 511 ms 8632 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 4 ms 8404 KB Output is correct
9 Correct 2563 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 38 ms 20692 KB Output is correct
2 Correct 20 ms 20648 KB Output is correct
3 Correct 28 ms 20652 KB Output is correct
4 Correct 50 ms 21360 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 8608 KB Output is correct
2 Correct 417 ms 8632 KB Output is correct
3 Correct 512 ms 8616 KB Output is correct
4 Correct 513 ms 8616 KB Output is correct
5 Correct 514 ms 8532 KB Output is correct
6 Correct 37 ms 20564 KB Output is correct
7 Correct 18 ms 20564 KB Output is correct
8 Correct 29 ms 20660 KB Output is correct
9 Correct 51 ms 21384 KB Output is correct
10 Correct 14 ms 16724 KB Output is correct
11 Correct 34 ms 16712 KB Output is correct
12 Correct 92 ms 18276 KB Output is correct
13 Correct 31 ms 16732 KB Output is correct
14 Correct 15 ms 16744 KB Output is correct
15 Correct 5 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 4 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 8460 KB Output is correct
22 Correct 5 ms 8404 KB Output is correct
23 Correct 4 ms 8404 KB Output is correct
24 Correct 4 ms 8404 KB Output is correct
25 Correct 66 ms 9476 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 2537 ms 8620 KB Output is correct
28 Correct 14019 ms 20984 KB Output is correct
29 Correct 9442 ms 18664 KB Output is correct
30 Correct 11643 ms 18644 KB Output is correct
31 Correct 9890 ms 22136 KB Output is correct
32 Correct 4 ms 8404 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 8620 KB Output is correct
2 Correct 419 ms 8612 KB Output is correct
3 Correct 517 ms 8736 KB Output is correct
4 Correct 515 ms 8616 KB Output is correct
5 Correct 520 ms 8548 KB Output is correct
6 Correct 38 ms 20564 KB Output is correct
7 Correct 17 ms 20568 KB Output is correct
8 Correct 31 ms 20656 KB Output is correct
9 Correct 51 ms 21324 KB Output is correct
10 Correct 15 ms 16744 KB Output is correct
11 Correct 35 ms 16748 KB Output is correct
12 Correct 101 ms 18232 KB Output is correct
13 Correct 25 ms 16744 KB Output is correct
14 Correct 15 ms 16724 KB Output is correct
15 Correct 820 ms 20628 KB Output is correct
16 Execution timed out 20043 ms 21448 KB Time limit exceeded
17 Halted 0 ms 0 KB -