oj.uz

Submission #679994

# Submission time Handle Problem Language Result Execution time Memory
679994 2023-01-09T18:31:03 Z bashkort Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 19088 KB 
#include <bits/stdc++.h>
#include "wombats.h"

using namespace std;

inline bool ckmin(int &a, int b) {
    return (a > b) && (a = b, true);
}

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 cc = 0; cc < c; ++cc) {
        function<void(int, int, int, int)> solve = [&](int l, int r, int optl, int optr) {
            if (l >= r) {
                return;
            }

            int mid = (l + r) >> 1;

            int opt = optl;

            for (int b = optl; b <= optr; ++b) {
                if (ckmin(dp[L][mid][cc], fr[L][mid][b] + V[(L + 1) * B - 1][b] + dp[L + 1][b][cc])) {
                    opt = b;
                }
            }

            solve(l, mid, optl, opt), solve(mid + 1, r, opt, optr);
        };
        solve(0, c, 0, c - 1);
    }

}

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 17 ms 13524 KB Output is correct
2 Correct 23 ms 13532 KB Output is correct
3 Correct 85 ms 15308 KB Output is correct
4 Correct 16 ms 13652 KB Output is correct
5 Correct 13 ms 13652 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 5 ms 8372 KB Output is correct
2 Correct 5 ms 8404 KB Output is correct
3 Correct 5 ms 8404 KB Output is correct
4 Correct 5 ms 8404 KB Output is correct
5 Correct 7 ms 8484 KB Output is correct
6 Correct 6 ms 8404 KB Output is correct
7 Correct 5 ms 8496 KB Output is correct
8 Correct 5 ms 8468 KB Output is correct
9 Correct 5 ms 8404 KB Output is correct
10 Correct 5 ms 8392 KB Output is correct
11 Correct 66 ms 9492 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 246 ms 8684 KB Output is correct
2 Correct 237 ms 8800 KB Output is correct
3 Correct 239 ms 8692 KB Output is correct
4 Correct 249 ms 8636 KB Output is correct
5 Correct 339 ms 8696 KB Output is correct
6 Correct 6 ms 8376 KB Output is correct
7 Correct 5 ms 8404 KB Output is correct
8 Correct 5 ms 8404 KB Output is correct
9 Correct 1203 ms 8684 KB Output is correct
10 Correct 5 ms 8404 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17592 KB Output is correct
2 Correct 28 ms 17472 KB Output is correct
3 Correct 25 ms 17476 KB Output is correct
4 Correct 53 ms 18368 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 8688 KB Output is correct
2 Correct 257 ms 8680 KB Output is correct
3 Correct 240 ms 8660 KB Output is correct
4 Correct 242 ms 8696 KB Output is correct
5 Correct 241 ms 8688 KB Output is correct
6 Correct 39 ms 17576 KB Output is correct
7 Correct 27 ms 17492 KB Output is correct
8 Correct 24 ms 17492 KB Output is correct
9 Correct 54 ms 18312 KB Output is correct
10 Correct 17 ms 13644 KB Output is correct
11 Correct 27 ms 13524 KB Output is correct
12 Correct 90 ms 15316 KB Output is correct
13 Correct 16 ms 13524 KB Output is correct
14 Correct 13 ms 13628 KB Output is correct
15 Correct 4 ms 8372 KB Output is correct
16 Correct 5 ms 8404 KB Output is correct
17 Correct 5 ms 8404 KB Output is correct
18 Correct 5 ms 8392 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 5 ms 8404 KB Output is correct
23 Correct 5 ms 8404 KB Output is correct
24 Correct 7 ms 8436 KB Output is correct
25 Correct 69 ms 9496 KB Output is correct
26 Correct 5 ms 8404 KB Output is correct
27 Correct 1167 ms 8692 KB Output is correct
28 Correct 12038 ms 18304 KB Output is correct
29 Correct 11310 ms 16756 KB Output is correct
30 Correct 10734 ms 16588 KB Output is correct
31 Correct 11520 ms 19088 KB Output is correct
32 Correct 5 ms 8404 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 8640 KB Output is correct
2 Correct 223 ms 8784 KB Output is correct
3 Correct 233 ms 8660 KB Output is correct
4 Correct 243 ms 8688 KB Output is correct
5 Correct 235 ms 8780 KB Output is correct
6 Correct 29 ms 17596 KB Output is correct
7 Correct 18 ms 17524 KB Output is correct
8 Correct 25 ms 17476 KB Output is correct
9 Correct 51 ms 18380 KB Output is correct
10 Correct 12 ms 13524 KB Output is correct
11 Correct 22 ms 13652 KB Output is correct
12 Correct 83 ms 15316 KB Output is correct
13 Correct 24 ms 13652 KB Output is correct
14 Correct 12 ms 13648 KB Output is correct
15 Correct 872 ms 17736 KB Output is correct
16 Execution timed out 20092 ms 18352 KB Time limit exceeded
17 Halted 0 ms 0 KB -