oj.uz

Submission #679966

# Submission time Handle Problem Language Result Execution time Memory
679966 2023-01-09T17:06:40 Z bashkort Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 20476 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 = 500, 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 13 ms 15060 KB Output is correct
2 Correct 31 ms 15060 KB Output is correct
3 Correct 85 ms 16704 KB Output is correct
4 Correct 20 ms 15192 KB Output is correct
5 Correct 17 ms 15060 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

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 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 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 5 ms 8444 KB Output is correct
10 Correct 5 ms 8404 KB Output is correct
11 Correct 64 ms 9468 KB Output is correct
12 Correct 4 ms 8468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 8620 KB Output is correct
2 Correct 411 ms 8620 KB Output is correct
3 Correct 514 ms 8600 KB Output is correct
4 Correct 515 ms 8624 KB Output is correct
5 Correct 501 ms 8636 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 8404 KB Output is correct
9 Correct 2523 ms 8636 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 34 ms 19096 KB Output is correct
2 Correct 17 ms 19028 KB Output is correct
3 Correct 31 ms 18976 KB Output is correct
4 Correct 54 ms 19852 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 8620 KB Output is correct
2 Correct 412 ms 8620 KB Output is correct
3 Correct 520 ms 8624 KB Output is correct
4 Correct 510 ms 8620 KB Output is correct
5 Correct 514 ms 8616 KB Output is correct
6 Correct 32 ms 19068 KB Output is correct
7 Correct 16 ms 19028 KB Output is correct
8 Correct 27 ms 19092 KB Output is correct
9 Correct 51 ms 19832 KB Output is correct
10 Correct 15 ms 15188 KB Output is correct
11 Correct 33 ms 15188 KB Output is correct
12 Correct 96 ms 16720 KB Output is correct
13 Correct 20 ms 15060 KB Output is correct
14 Correct 14 ms 15184 KB Output is correct
15 Correct 4 ms 8404 KB Output is correct
16 Correct 5 ms 8404 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 5 ms 8492 KB Output is correct
21 Correct 4 ms 8404 KB Output is correct
22 Correct 6 ms 8408 KB Output is correct
23 Correct 5 ms 8404 KB Output is correct
24 Correct 4 ms 8404 KB Output is correct
25 Correct 66 ms 9500 KB Output is correct
26 Correct 5 ms 8404 KB Output is correct
27 Correct 2524 ms 8620 KB Output is correct
28 Correct 16747 ms 19452 KB Output is correct
29 Correct 12565 ms 17760 KB Output is correct
30 Correct 13085 ms 17640 KB Output is correct
31 Correct 13731 ms 20476 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 556 ms 8616 KB Output is correct
2 Correct 437 ms 8532 KB Output is correct
3 Correct 530 ms 8620 KB Output is correct
4 Correct 540 ms 8640 KB Output is correct
5 Correct 528 ms 8632 KB Output is correct
6 Correct 34 ms 19096 KB Output is correct
7 Correct 17 ms 19028 KB Output is correct
8 Correct 25 ms 19028 KB Output is correct
9 Correct 49 ms 19804 KB Output is correct
10 Correct 16 ms 15188 KB Output is correct
11 Correct 27 ms 15188 KB Output is correct
12 Correct 89 ms 16712 KB Output is correct
13 Correct 28 ms 15168 KB Output is correct
14 Correct 14 ms 15192 KB Output is correct
15 Correct 916 ms 19072 KB Output is correct
16 Execution timed out 20058 ms 19716 KB Time limit exceeded
17 Halted 0 ms 0 KB -