oj.uz

Submission #679963

# Submission time Handle Problem Language Result Execution time Memory
679963 2023-01-09T17:04:10 Z bashkort Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 32516 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 = 100, 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 29 ms 27604 KB Output is correct
2 Correct 193 ms 27696 KB Output is correct
3 Correct 216 ms 29232 KB Output is correct
4 Correct 86 ms 27604 KB Output is correct
5 Correct 26 ms 27712 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

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 5 ms 8404 KB Output is correct
6 Correct 5 ms 8404 KB Output is correct
7 Correct 4 ms 8392 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 4 ms 8404 KB Output is correct
10 Correct 4 ms 8404 KB Output is correct
11 Correct 68 ms 9436 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 454 ms 8620 KB Output is correct
2 Correct 414 ms 8616 KB Output is correct
3 Correct 456 ms 8652 KB Output is correct
4 Correct 487 ms 8712 KB Output is correct
5 Correct 447 ms 8532 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 4 ms 8436 KB Output is correct
8 Correct 4 ms 8404 KB Output is correct
9 Correct 2410 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 223 ms 31596 KB Output is correct
2 Correct 30 ms 31616 KB Output is correct
3 Correct 100 ms 31640 KB Output is correct
4 Correct 60 ms 32332 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 8616 KB Output is correct
2 Correct 415 ms 8620 KB Output is correct
3 Correct 454 ms 8616 KB Output is correct
4 Correct 454 ms 8632 KB Output is correct
5 Correct 450 ms 8620 KB Output is correct
6 Correct 227 ms 31572 KB Output is correct
7 Correct 35 ms 31572 KB Output is correct
8 Correct 90 ms 31596 KB Output is correct
9 Correct 60 ms 32292 KB Output is correct
10 Correct 31 ms 27716 KB Output is correct
11 Correct 180 ms 27692 KB Output is correct
12 Correct 238 ms 29236 KB Output is correct
13 Correct 89 ms 27688 KB Output is correct
14 Correct 26 ms 27596 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 5 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 4 ms 8404 KB Output is correct
23 Correct 5 ms 8404 KB Output is correct
24 Correct 4 ms 8404 KB Output is correct
25 Correct 70 ms 9388 KB Output is correct
26 Correct 4 ms 8404 KB Output is correct
27 Correct 2380 ms 8636 KB Output is correct
28 Execution timed out 20023 ms 32252 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 8612 KB Output is correct
2 Correct 422 ms 8532 KB Output is correct
3 Correct 458 ms 8628 KB Output is correct
4 Correct 460 ms 8652 KB Output is correct
5 Correct 448 ms 8628 KB Output is correct
6 Correct 184 ms 31600 KB Output is correct
7 Correct 28 ms 31592 KB Output is correct
8 Correct 88 ms 31572 KB Output is correct
9 Correct 60 ms 32312 KB Output is correct
10 Correct 27 ms 27708 KB Output is correct
11 Correct 187 ms 27692 KB Output is correct
12 Correct 223 ms 29236 KB Output is correct
13 Correct 88 ms 27604 KB Output is correct
14 Correct 27 ms 27604 KB Output is correct
15 Correct 947 ms 31612 KB Output is correct
16 Execution timed out 20051 ms 32516 KB Time limit exceeded
17 Halted 0 ms 0 KB -