oj.uz

Submission #679957

# Submission time Handle Problem Language Result Execution time Memory
679957 2023-01-09T16:56:40 Z bashkort Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 27252 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 = 1000, 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 13524 KB Output is correct
2 Correct 27 ms 13636 KB Output is correct
3 Correct 89 ms 16392 KB Output is correct
4 Correct 16 ms 13556 KB Output is correct
5 Correct 13 ms 13524 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 6 ms 8404 KB Output is correct
8 Correct 5 ms 8372 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8416 KB Output is correct
2 Correct 5 ms 8440 KB Output is correct
3 Correct 5 ms 8404 KB Output is correct
4 Correct 5 ms 8404 KB Output is correct
5 Correct 5 ms 8440 KB Output is correct
6 Correct 5 ms 8436 KB Output is correct
7 Correct 6 ms 8404 KB Output is correct
8 Correct 6 ms 8404 KB Output is correct
9 Correct 5 ms 8404 KB Output is correct
10 Correct 4 ms 8404 KB Output is correct
11 Correct 67 ms 9396 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 539 ms 8704 KB Output is correct
2 Correct 435 ms 8608 KB Output is correct
3 Correct 530 ms 8508 KB Output is correct
4 Correct 549 ms 8612 KB Output is correct
5 Correct 538 ms 8616 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 6 ms 8404 KB Output is correct
9 Correct 2634 ms 8608 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 17464 KB Output is correct
2 Correct 20 ms 17496 KB Output is correct
3 Correct 24 ms 17584 KB Output is correct
4 Correct 51 ms 18884 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 8612 KB Output is correct
2 Correct 413 ms 8612 KB Output is correct
3 Correct 549 ms 8652 KB Output is correct
4 Correct 522 ms 8628 KB Output is correct
5 Correct 524 ms 8612 KB Output is correct
6 Correct 26 ms 17492 KB Output is correct
7 Correct 18 ms 17492 KB Output is correct
8 Correct 23 ms 17596 KB Output is correct
9 Correct 60 ms 18904 KB Output is correct
10 Correct 12 ms 13628 KB Output is correct
11 Correct 19 ms 13564 KB Output is correct
12 Correct 80 ms 16412 KB Output is correct
13 Correct 18 ms 13648 KB Output is correct
14 Correct 12 ms 13648 KB Output is correct
15 Correct 5 ms 8372 KB Output is correct
16 Correct 4 ms 8376 KB Output is correct
17 Correct 5 ms 8404 KB Output is correct
18 Correct 5 ms 8504 KB Output is correct
19 Correct 5 ms 8504 KB Output is correct
20 Correct 6 ms 8512 KB Output is correct
21 Correct 5 ms 8404 KB Output is correct
22 Correct 5 ms 8408 KB Output is correct
23 Correct 5 ms 8412 KB Output is correct
24 Correct 5 ms 8404 KB Output is correct
25 Correct 67 ms 10816 KB Output is correct
26 Correct 5 ms 8404 KB Output is correct
27 Correct 2568 ms 8708 KB Output is correct
28 Execution timed out 20070 ms 21680 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 8620 KB Output is correct
2 Correct 427 ms 8632 KB Output is correct
3 Correct 535 ms 8612 KB Output is correct
4 Correct 518 ms 8532 KB Output is correct
5 Correct 540 ms 8612 KB Output is correct
6 Correct 25 ms 17508 KB Output is correct
7 Correct 17 ms 17492 KB Output is correct
8 Correct 28 ms 17468 KB Output is correct
9 Correct 50 ms 18924 KB Output is correct
10 Correct 13 ms 13636 KB Output is correct
11 Correct 23 ms 13752 KB Output is correct
12 Correct 83 ms 16332 KB Output is correct
13 Correct 16 ms 13524 KB Output is correct
14 Correct 12 ms 13524 KB Output is correct
15 Correct 1002 ms 27252 KB Output is correct
16 Execution timed out 20070 ms 25820 KB Time limit exceeded
17 Halted 0 ms 0 KB -