oj.uz

Submission #603839

# Submission time Handle Problem Language Result Execution time Memory
603839 2022-07-24T12:20:44 Z KoD Wombats (IOI13_wombats) C++17
100 / 100
 3026 ms 176044 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "wombats.h"
#include <bits/stdc++.h>

using std::array;

constexpr int INF = (1 << 30) - 1;
const int MAX_R = 5000;
const int MAX_C = 200;
const int BLOCK = 10;
const int SEG = 512;

template <class T>
bool setmin(T& x, const T& y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

// grid data
int R, C;
int H[MAX_R][MAX_C];
int V[MAX_R][MAX_C];

// segtree data
array<array<int, MAX_C>, MAX_C> dist[2 * SEG];
int append[2 * SEG];

void calc_group(const int g) {
    const int i0 = BLOCK * g;
    const int i1 = std::min(R, i0 + BLOCK);
    static array<int, MAX_C> accum = {};
    static array<int, MAX_C> next = {};
    const auto setup = [&](const int i) {
        for (int j = 0; j < C - 1; ++j)
            accum[j + 1] = accum[j] + H[i][j];
    };
    setup(i0);
    auto& dp = dist[SEG + g];
    for (int a = 0; a < C; ++a)
        for (int b = a; b < C; ++b)
            dp[a][b] = dp[b][a] = accum[b] - accum[a];
    for (int i = i0; i < i1 - 1; ++i) {
        setup(i + 1);
        for (int a = 0; a < C; ++a) {
            next.fill(INF);
            for (int b = 0, min = INF; b < C; ++b) {
                setmin(min, dp[a][b] + V[i][b] - accum[b]);
                setmin(next[b], min + accum[b]);
            }
            for (int b = C - 1, min = INF; b >= 0; --b) {
                setmin(min, dp[a][b] + V[i][b] + accum[b]);
                setmin(next[b], min - accum[b]);
            }
            dp[a] = next;
        }
    }
}

void fetch(const int g) {
    const int l = 2 * g;
    const int r = 2 * g + 1;
    append[g] = append[r];
    if (append[l] == R - 1) {
        dist[g] = dist[l];
        return;
    }
    auto& dp = dist[g];
    for (int a = 0; a < C; ++a)
        for (int b = 0; b < C; ++b)
            dp[a][b] = INF;
    static array<array<int, MAX_C>, MAX_C> best = {};
    const auto check = [&](const int a, const int c, const int b) {
        if (setmin(dp[a][b], dist[l][a][c] + V[append[l]][c] + dist[r][c][b]))
            best[a][b] = c;
    };
    for (int a = 0; a < C; ++a)
        for (int b = 0; b < C; ++b)
            check(a, b, a);
    for (int len = 1; len < C; ++len) {
        for (int a = 0; a + len < C; ++a)
            for (int b = best[a][a + len - 1]; b <= best[a + 1][a + len]; ++b)
                check(a, b, a + len);
        for (int a = len; a < C; ++a)
            for (int b = best[a - 1][a - len]; b <= best[a][a - len + 1]; ++b)
                check(a, b, a - len);
    }
}

void init(int r, int c, int h[MAX_R][MAX_C], int v[MAX_R][MAX_C]) {
    R = r, C = c;
    std::memcpy(H, h, sizeof(H));
    std::memcpy(V, v, sizeof(V));
    const int n = (R + BLOCK - 1) / BLOCK;
    for (int g = 0; g < n; ++g)
        calc_group(g);
    for (int g = 0; g < SEG; ++g)
        append[SEG + g] = std::min(BLOCK * (g + 1) - 1, R - 1);
    for (int g = SEG - 1; g > 0; --g)
        fetch(g);
}

void changeH(int p, int q, int w) {
    H[p][q] = w;
    const int g = p / BLOCK;
    calc_group(g);
    for (int k = SEG + g; (k >>= 1) > 0;)
        fetch(k);
}

void changeV(int p, int q, int w) {
    V[p][q] = w;
    const int g = p / BLOCK;
    calc_group(g);
    for (int k = SEG + g; (k >>= 1) > 0;)
        fetch(k);
}

int escape(int v0, int v1) {
    return dist[1][v0][v1];
}

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 10 ms 18516 KB Output is correct
2 Correct 12 ms 18640 KB Output is correct
3 Correct 78 ms 20280 KB Output is correct
4 Correct 11 ms 18604 KB Output is correct
5 Correct 11 ms 18516 KB Output is correct
6 Correct 42 ms 88244 KB Output is correct
7 Correct 44 ms 88336 KB Output is correct
8 Correct 40 ms 88256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 88276 KB Output is correct
2 Correct 43 ms 88296 KB Output is correct
3 Correct 44 ms 88300 KB Output is correct
4 Correct 40 ms 88132 KB Output is correct
5 Correct 39 ms 88196 KB Output is correct
6 Correct 45 ms 88216 KB Output is correct
7 Correct 40 ms 88272 KB Output is correct
8 Correct 40 ms 88172 KB Output is correct
9 Correct 47 ms 88140 KB Output is correct
10 Correct 40 ms 88232 KB Output is correct
11 Correct 105 ms 89184 KB Output is correct
12 Correct 40 ms 88176 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 88628 KB Output is correct
2 Correct 98 ms 88684 KB Output is correct
3 Correct 118 ms 88652 KB Output is correct
4 Correct 121 ms 88620 KB Output is correct
5 Correct 121 ms 88680 KB Output is correct
6 Correct 39 ms 88268 KB Output is correct
7 Correct 40 ms 88260 KB Output is correct
8 Correct 39 ms 88224 KB Output is correct
9 Correct 321 ms 88704 KB Output is correct
10 Correct 44 ms 88268 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23264 KB Output is correct
2 Correct 15 ms 23284 KB Output is correct
3 Correct 16 ms 23232 KB Output is correct
4 Correct 47 ms 23944 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 88704 KB Output is correct
2 Correct 106 ms 88680 KB Output is correct
3 Correct 120 ms 88700 KB Output is correct
4 Correct 120 ms 88652 KB Output is correct
5 Correct 121 ms 88604 KB Output is correct
6 Correct 14 ms 23252 KB Output is correct
7 Correct 17 ms 23180 KB Output is correct
8 Correct 16 ms 23252 KB Output is correct
9 Correct 51 ms 23992 KB Output is correct
10 Correct 11 ms 18592 KB Output is correct
11 Correct 11 ms 18624 KB Output is correct
12 Correct 73 ms 20108 KB Output is correct
13 Correct 10 ms 18516 KB Output is correct
14 Correct 12 ms 18588 KB Output is correct
15 Correct 40 ms 88256 KB Output is correct
16 Correct 41 ms 88268 KB Output is correct
17 Correct 40 ms 88296 KB Output is correct
18 Correct 44 ms 88136 KB Output is correct
19 Correct 39 ms 88136 KB Output is correct
20 Correct 45 ms 88148 KB Output is correct
21 Correct 39 ms 88240 KB Output is correct
22 Correct 40 ms 88168 KB Output is correct
23 Correct 40 ms 88184 KB Output is correct
24 Correct 40 ms 88236 KB Output is correct
25 Correct 101 ms 89184 KB Output is correct
26 Correct 40 ms 88232 KB Output is correct
27 Correct 316 ms 88700 KB Output is correct
28 Correct 716 ms 100508 KB Output is correct
29 Correct 805 ms 98556 KB Output is correct
30 Correct 835 ms 98516 KB Output is correct
31 Correct 816 ms 101556 KB Output is correct
32 Correct 41 ms 88304 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 88700 KB Output is correct
2 Correct 104 ms 88676 KB Output is correct
3 Correct 122 ms 88700 KB Output is correct
4 Correct 126 ms 88628 KB Output is correct
5 Correct 119 ms 88652 KB Output is correct
6 Correct 14 ms 23252 KB Output is correct
7 Correct 15 ms 23288 KB Output is correct
8 Correct 14 ms 23264 KB Output is correct
9 Correct 45 ms 24008 KB Output is correct
10 Correct 13 ms 18516 KB Output is correct
11 Correct 10 ms 18616 KB Output is correct
12 Correct 76 ms 20128 KB Output is correct
13 Correct 13 ms 18516 KB Output is correct
14 Correct 14 ms 18504 KB Output is correct
15 Correct 926 ms 174416 KB Output is correct
16 Correct 3026 ms 176044 KB Output is correct
17 Correct 41 ms 88188 KB Output is correct
18 Correct 39 ms 88204 KB Output is correct
19 Correct 39 ms 88232 KB Output is correct
20 Correct 42 ms 88212 KB Output is correct
21 Correct 40 ms 88192 KB Output is correct
22 Correct 41 ms 88124 KB Output is correct
23 Correct 42 ms 88140 KB Output is correct
24 Correct 50 ms 88244 KB Output is correct
25 Correct 41 ms 88144 KB Output is correct
26 Correct 42 ms 88248 KB Output is correct
27 Correct 100 ms 89164 KB Output is correct
28 Correct 40 ms 88144 KB Output is correct
29 Correct 325 ms 88700 KB Output is correct
30 Correct 709 ms 100432 KB Output is correct
31 Correct 2305 ms 175036 KB Output is correct
32 Correct 2477 ms 175112 KB Output is correct
33 Correct 797 ms 98372 KB Output is correct
34 Correct 2758 ms 159608 KB Output is correct
35 Correct 919 ms 98496 KB Output is correct
36 Correct 2686 ms 159620 KB Output is correct
37 Correct 792 ms 101548 KB Output is correct
38 Correct 2448 ms 175740 KB Output is correct
39 Correct 40 ms 88268 KB Output is correct
40 Correct 2871 ms 159588 KB Output is correct