oj.uz

Submission #679962

# Submission time Handle Problem Language Result Execution time Memory
679962 2023-01-09T17:02:18 Z bashkort Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 48028 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 = 50, 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 58 ms 43348 KB Output is correct
2 Correct 729 ms 43344 KB Output is correct
3 Correct 782 ms 44876 KB Output is correct
4 Correct 361 ms 43348 KB Output is correct
5 Correct 44 ms 43260 KB Output is correct
6 Correct 4 ms 8404 KB Output is correct
7 Correct 6 ms 8404 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8404 KB Output is correct
2 Correct 4 ms 8404 KB Output is correct
3 Correct 6 ms 8404 KB Output is correct
4 Correct 5 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 5 ms 8404 KB Output is correct
8 Correct 4 ms 8400 KB Output is correct
9 Correct 5 ms 8440 KB Output is correct
10 Correct 5 ms 8512 KB Output is correct
11 Correct 70 ms 9452 KB Output is correct
12 Correct 5 ms 8504 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 8928 KB Output is correct
2 Correct 303 ms 8928 KB Output is correct
3 Correct 340 ms 8928 KB Output is correct
4 Correct 333 ms 8960 KB Output is correct
5 Correct 326 ms 8944 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 1610 ms 8928 KB Output is correct
10 Correct 6 ms 8404 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 47248 KB Output is correct
2 Correct 47 ms 47244 KB Output is correct
3 Correct 353 ms 47180 KB Output is correct
4 Correct 90 ms 47964 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 9056 KB Output is correct
2 Correct 299 ms 8932 KB Output is correct
3 Correct 329 ms 8916 KB Output is correct
4 Correct 329 ms 9036 KB Output is correct
5 Correct 320 ms 8928 KB Output is correct
6 Correct 730 ms 47252 KB Output is correct
7 Correct 49 ms 47188 KB Output is correct
8 Correct 378 ms 47252 KB Output is correct
9 Correct 80 ms 47996 KB Output is correct
10 Correct 45 ms 43344 KB Output is correct
11 Correct 767 ms 43348 KB Output is correct
12 Correct 809 ms 44912 KB Output is correct
13 Correct 340 ms 43348 KB Output is correct
14 Correct 49 ms 43348 KB Output is correct
15 Correct 4 ms 8404 KB Output is correct
16 Correct 5 ms 8456 KB Output is correct
17 Correct 5 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 4 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 5 ms 8404 KB Output is correct
25 Correct 69 ms 9472 KB Output is correct
26 Correct 5 ms 8404 KB Output is correct
27 Correct 1650 ms 8932 KB Output is correct
28 Execution timed out 20104 ms 47396 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 8916 KB Output is correct
2 Correct 295 ms 8916 KB Output is correct
3 Correct 340 ms 8928 KB Output is correct
4 Correct 334 ms 8924 KB Output is correct
5 Correct 359 ms 8928 KB Output is correct
6 Correct 733 ms 47248 KB Output is correct
7 Correct 55 ms 47256 KB Output is correct
8 Correct 356 ms 47252 KB Output is correct
9 Correct 83 ms 48028 KB Output is correct
10 Correct 61 ms 43220 KB Output is correct
11 Correct 773 ms 43344 KB Output is correct
12 Correct 833 ms 44876 KB Output is correct
13 Correct 349 ms 43348 KB Output is correct
14 Correct 59 ms 43340 KB Output is correct
15 Correct 1317 ms 47176 KB Output is correct
16 Execution timed out 20060 ms 47904 KB Time limit exceeded
17 Halted 0 ms 0 KB -