oj.uz

Submission #679959

# Submission time Handle Problem Language Result Execution time Memory
679959 2023-01-09T16:57:41 Z bashkort Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 17684 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 = 2000, 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 17 ms 13000 KB Output is correct
2 Correct 16 ms 12992 KB Output is correct
3 Correct 77 ms 14540 KB Output is correct
4 Correct 18 ms 13004 KB Output is correct
5 Correct 14 ms 12884 KB Output is correct
6 Correct 6 ms 8448 KB Output is correct
7 Correct 6 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 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 4 ms 8404 KB Output is correct
5 Correct 4 ms 8404 KB Output is correct
6 Correct 6 ms 8404 KB Output is correct
7 Correct 6 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 7 ms 8404 KB Output is correct
11 Correct 73 ms 9420 KB Output is correct
12 Correct 5 ms 8396 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 8608 KB Output is correct
2 Correct 419 ms 8616 KB Output is correct
3 Correct 516 ms 8612 KB Output is correct
4 Correct 509 ms 8660 KB Output is correct
5 Correct 505 ms 8628 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 2547 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 26 ms 16900 KB Output is correct
2 Correct 20 ms 16896 KB Output is correct
3 Correct 27 ms 16900 KB Output is correct
4 Correct 61 ms 17676 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 8736 KB Output is correct
2 Correct 408 ms 8612 KB Output is correct
3 Correct 515 ms 8612 KB Output is correct
4 Correct 507 ms 8612 KB Output is correct
5 Correct 510 ms 8616 KB Output is correct
6 Correct 22 ms 16852 KB Output is correct
7 Correct 20 ms 16904 KB Output is correct
8 Correct 25 ms 16856 KB Output is correct
9 Correct 58 ms 17684 KB Output is correct
10 Correct 13 ms 12992 KB Output is correct
11 Correct 21 ms 12992 KB Output is correct
12 Correct 80 ms 14520 KB Output is correct
13 Correct 14 ms 12996 KB Output is correct
14 Correct 13 ms 12996 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 4 ms 8404 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 4 ms 8404 KB Output is correct
24 Correct 5 ms 8404 KB Output is correct
25 Correct 64 ms 9380 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 2528 ms 8632 KB Output is correct
28 Execution timed out 20084 ms 17140 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 8616 KB Output is correct
2 Correct 411 ms 8532 KB Output is correct
3 Correct 510 ms 8616 KB Output is correct
4 Correct 524 ms 8616 KB Output is correct
5 Correct 511 ms 8532 KB Output is correct
6 Correct 23 ms 16852 KB Output is correct
7 Correct 21 ms 16852 KB Output is correct
8 Correct 28 ms 16900 KB Output is correct
9 Correct 55 ms 17636 KB Output is correct
10 Correct 13 ms 12884 KB Output is correct
11 Correct 15 ms 12976 KB Output is correct
12 Correct 75 ms 14472 KB Output is correct
13 Correct 14 ms 12884 KB Output is correct
14 Correct 13 ms 12884 KB Output is correct
15 Correct 1305 ms 16992 KB Output is correct
16 Execution timed out 20096 ms 16900 KB Time limit exceeded
17 Halted 0 ms 0 KB -