oj.uz

Submission #679968

# Submission time Handle Problem Language Result Execution time Memory
679968 2023-01-09T17:09:19 Z bashkort Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 18808 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 a = 0; a < c - 1; ++a) {
            for (int cc = 0; cc < c; ++cc)
                ckmin(fr[L][a + 1][cc], fr[L][a][cc] + H[i][a]);
        }
        for (int a = c - 2; a >= 0; --a) {
            for (int cc = 0; cc < c; ++cc)
                ckmin(fr[L][a][cc], fr[L][a + 1][cc] + H[i][a]);
        }
        if (i != lim) {
            for (int cc = 0; cc < c; ++cc) {
                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 12 ms 13524 KB Output is correct
2 Correct 22 ms 13600 KB Output is correct
3 Correct 84 ms 15128 KB Output is correct
4 Correct 16 ms 13620 KB Output is correct
5 Correct 15 ms 13568 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 6 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 6 ms 8388 KB Output is correct
2 Correct 5 ms 8404 KB Output is correct
3 Correct 5 ms 8404 KB Output is correct
4 Correct 6 ms 8400 KB Output is correct
5 Correct 5 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 5 ms 8480 KB Output is correct
10 Correct 5 ms 8404 KB Output is correct
11 Correct 68 ms 9400 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 238 ms 8616 KB Output is correct
2 Correct 242 ms 8608 KB Output is correct
3 Correct 278 ms 8568 KB Output is correct
4 Correct 237 ms 8532 KB Output is correct
5 Correct 237 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 4 ms 8404 KB Output is correct
9 Correct 1231 ms 8628 KB Output is correct
10 Correct 4 ms 8408 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 17440 KB Output is correct
2 Correct 18 ms 17524 KB Output is correct
3 Correct 23 ms 17524 KB Output is correct
4 Correct 61 ms 18192 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 8532 KB Output is correct
2 Correct 225 ms 8608 KB Output is correct
3 Correct 249 ms 8612 KB Output is correct
4 Correct 247 ms 8632 KB Output is correct
5 Correct 243 ms 8612 KB Output is correct
6 Correct 30 ms 17524 KB Output is correct
7 Correct 19 ms 17528 KB Output is correct
8 Correct 31 ms 17468 KB Output is correct
9 Correct 52 ms 18212 KB Output is correct
10 Correct 12 ms 13524 KB Output is correct
11 Correct 20 ms 13524 KB Output is correct
12 Correct 85 ms 15112 KB Output is correct
13 Correct 16 ms 13524 KB Output is correct
14 Correct 12 ms 13620 KB Output is correct
15 Correct 5 ms 8404 KB Output is correct
16 Correct 4 ms 8416 KB Output is correct
17 Correct 4 ms 8404 KB Output is correct
18 Correct 5 ms 8404 KB Output is correct
19 Correct 5 ms 8404 KB Output is correct
20 Correct 6 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 5 ms 8392 KB Output is correct
24 Correct 5 ms 8404 KB Output is correct
25 Correct 67 ms 9400 KB Output is correct
26 Correct 5 ms 8404 KB Output is correct
27 Correct 1162 ms 8608 KB Output is correct
28 Correct 13295 ms 17868 KB Output is correct
29 Correct 11533 ms 16496 KB Output is correct
30 Correct 11654 ms 16560 KB Output is correct
31 Correct 11719 ms 18808 KB Output is correct
32 Correct 5 ms 8408 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 8612 KB Output is correct
2 Correct 224 ms 8612 KB Output is correct
3 Correct 268 ms 8612 KB Output is correct
4 Correct 252 ms 8532 KB Output is correct
5 Correct 233 ms 8624 KB Output is correct
6 Correct 26 ms 17524 KB Output is correct
7 Correct 18 ms 17520 KB Output is correct
8 Correct 23 ms 17492 KB Output is correct
9 Correct 56 ms 18296 KB Output is correct
10 Correct 12 ms 13616 KB Output is correct
11 Correct 19 ms 13620 KB Output is correct
12 Correct 81 ms 15184 KB Output is correct
13 Correct 16 ms 13616 KB Output is correct
14 Correct 14 ms 13576 KB Output is correct
15 Correct 890 ms 17588 KB Output is correct
16 Execution timed out 20088 ms 18268 KB Time limit exceeded
17 Halted 0 ms 0 KB -