oj.uz

Submission #415010

# Submission time Handle Problem Language Result Execution time Memory
415010 2021-05-31T12:23:37 Z KoD Wombats (IOI13_wombats) C++17
100 / 100
 6345 ms 174828 KB 
#include <bits/stdc++.h>
#include "wombats.h"

constexpr int LOG = 10;
constexpr int INF = 1000000000;
constexpr int RMAX = 5000;
constexpr int CMAX = 200;
constexpr int SEGMAX = 512;

bool chmin(int& x, const int y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int R, C;
int hori[RMAX][CMAX], vert[RMAX][CMAX];

int size;
int dist[2 * SEGMAX][CMAX][CMAX];
int right[2 * SEGMAX];
int cumsum[CMAX];
int base[CMAX][CMAX], next[CMAX][CMAX];
int idx[CMAX][CMAX];
bool reached[2 * SEGMAX];

void setup(const int i) {
    for (int j = 0; j < C - 1; ++j) 
        cumsum[j + 1] = cumsum[j] + hori[i][j];
    for (int j = 0; j < C; ++j) 
        for (int k = 0; k < C; ++k)
            base[j][k] = std::abs(cumsum[k] - cumsum[j]);
}

void absorb(const int i, const int m) {
    for (int j = 0; j < C; ++j)
        for (int k = 0; k < C; ++k)
            next[j][k] = INF;
    for (int j = 0; j < C; ++j)
        for (int k = 0; k < C; ++k)
            if (chmin(next[j][j], dist[i][j][k] + vert[m][k] + base[k][j]))
                idx[j][j] = k;
    for (int l = 1; l < C; ++l) {
        for (int j = 0; j + l < C; ++j)
            for (int k = idx[j][j + l - 1]; k <= idx[j + 1][j + l]; ++k)
                if (chmin(next[j][j + l], dist[i][j][k] + vert[m][k] + base[k][j + l]))
                    idx[j][j + l] = k;
        for (int j = l; j < C; ++j)
            for (int k = idx[j - 1][j - l]; k <= idx[j][j - l + 1]; ++k)
                if (chmin(next[j][j - l], dist[i][j][k] + vert[m][k] + base[k][j - l]))
                    idx[j][j - l] = k;
    }
    std::memcpy(dist[i], next, sizeof(dist[i]));
}

void fetch(const int k) {
    if (reached[2 * k]) {
        reached[k] = true;
        std::memcpy(dist[k], dist[2 * k], sizeof(dist[k]));
        right[k] = right[2 * k];
        if (reached[2 * k + 1]) {
            std::memcpy(base, dist[2 * k + 1], sizeof(base));
            absorb(k, right[k]);
            right[k] = right[2 * k + 1];
        }
    }
}

void update(int k) {
    k += SEGMAX;
    while (k > 1) {
        k >>= 1;
        fetch(k);
    }
}

void recalc(const int i) {
    const int up = LOG * i;
    const int down = std::min(up + LOG, R);
    setup(up);
    std::memcpy(dist[SEGMAX + i], base, sizeof(dist[SEGMAX + i]));
    right[SEGMAX + i] = down - 1;
    for (int j = up + 1; j < down; ++j) {
        setup(j);
        absorb(SEGMAX + i, j - 1);
    }
}

void init(int N, int M, int H[RMAX][CMAX], int V[RMAX][CMAX]) {
    R = N, C = M;
    for (int i = 0; i < R; ++i) 
        for (int j = 0; j < C - 1; ++j) 
            hori[i][j] = H[i][j];
    for (int i = 0; i < R - 1; ++i) 
        for (int j = 0; j < C; ++j) 
            vert[i][j] = V[i][j];
    size = (R + LOG - 1) / LOG;
    for (int i = 0; i < size; ++i) {
        recalc(i);
        reached[SEGMAX + i] = true;
    }
    for (int i = SEGMAX - 1; i > 0; --i) {
        fetch(i);
    }
}

void changeH(int P, int Q, int W) {
    hori[P][Q] = W;
    recalc(P / LOG);
    update(P / LOG);
}

void changeV(int P, int Q, int W) {
    vert[P][Q] = W;
    recalc(P / LOG);
    update(P / LOG);
}

int escape(int V1, int V2) {
    return dist[1][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 323 ms 165016 KB Output is correct
2 Correct 333 ms 164968 KB Output is correct
3 Correct 372 ms 166520 KB Output is correct
4 Correct 346 ms 165120 KB Output is correct
5 Correct 290 ms 165008 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 2 ms 1868 KB Output is correct
8 Correct 2 ms 1868 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 3 ms 2252 KB Output is correct
5 Correct 2 ms 2252 KB Output is correct
6 Correct 2 ms 2252 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 4 ms 2252 KB Output is correct
9 Correct 4 ms 2252 KB Output is correct
10 Correct 4 ms 2252 KB Output is correct
11 Correct 79 ms 3240 KB Output is correct
12 Correct 3 ms 2252 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 5024 KB Output is correct
2 Correct 137 ms 5068 KB Output is correct
3 Correct 186 ms 5068 KB Output is correct
4 Correct 188 ms 5076 KB Output is correct
5 Correct 180 ms 5068 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 2 ms 1868 KB Output is correct
8 Correct 2 ms 1868 KB Output is correct
9 Correct 635 ms 5072 KB Output is correct
10 Correct 2 ms 1868 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 172832 KB Output is correct
2 Correct 340 ms 172868 KB Output is correct
3 Correct 318 ms 172840 KB Output is correct
4 Correct 376 ms 173608 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 5080 KB Output is correct
2 Correct 149 ms 4988 KB Output is correct
3 Correct 182 ms 5068 KB Output is correct
4 Correct 184 ms 5016 KB Output is correct
5 Correct 193 ms 5068 KB Output is correct
6 Correct 296 ms 172832 KB Output is correct
7 Correct 316 ms 172864 KB Output is correct
8 Correct 317 ms 172844 KB Output is correct
9 Correct 387 ms 173508 KB Output is correct
10 Correct 314 ms 165188 KB Output is correct
11 Correct 321 ms 165096 KB Output is correct
12 Correct 370 ms 166552 KB Output is correct
13 Correct 349 ms 165060 KB Output is correct
14 Correct 309 ms 165108 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct
16 Correct 2 ms 1868 KB Output is correct
17 Correct 2 ms 1868 KB Output is correct
18 Correct 3 ms 2252 KB Output is correct
19 Correct 3 ms 2252 KB Output is correct
20 Correct 2 ms 2252 KB Output is correct
21 Correct 3 ms 2252 KB Output is correct
22 Correct 2 ms 2252 KB Output is correct
23 Correct 3 ms 2252 KB Output is correct
24 Correct 3 ms 2252 KB Output is correct
25 Correct 80 ms 3248 KB Output is correct
26 Correct 3 ms 2252 KB Output is correct
27 Correct 634 ms 4968 KB Output is correct
28 Correct 1705 ms 173536 KB Output is correct
29 Correct 1867 ms 142880 KB Output is correct
30 Correct 1786 ms 142876 KB Output is correct
31 Correct 1655 ms 174280 KB Output is correct
32 Correct 2 ms 1868 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 4964 KB Output is correct
2 Correct 143 ms 5064 KB Output is correct
3 Correct 194 ms 5076 KB Output is correct
4 Correct 179 ms 5080 KB Output is correct
5 Correct 178 ms 5068 KB Output is correct
6 Correct 303 ms 172832 KB Output is correct
7 Correct 332 ms 172868 KB Output is correct
8 Correct 311 ms 172980 KB Output is correct
9 Correct 382 ms 173740 KB Output is correct
10 Correct 323 ms 164936 KB Output is correct
11 Correct 299 ms 164896 KB Output is correct
12 Correct 383 ms 166596 KB Output is correct
13 Correct 318 ms 165072 KB Output is correct
14 Correct 289 ms 165064 KB Output is correct
15 Correct 2200 ms 173156 KB Output is correct
16 Correct 6345 ms 174828 KB Output is correct
17 Correct 2 ms 1868 KB Output is correct
18 Correct 2 ms 1868 KB Output is correct
19 Correct 2 ms 1868 KB Output is correct
20 Correct 3 ms 2252 KB Output is correct
21 Correct 3 ms 2252 KB Output is correct
22 Correct 2 ms 2252 KB Output is correct
23 Correct 3 ms 2260 KB Output is correct
24 Correct 3 ms 2252 KB Output is correct
25 Correct 2 ms 2252 KB Output is correct
26 Correct 3 ms 2252 KB Output is correct
27 Correct 76 ms 3308 KB Output is correct
28 Correct 2 ms 2252 KB Output is correct
29 Correct 659 ms 5072 KB Output is correct
30 Correct 1541 ms 173512 KB Output is correct
31 Correct 5194 ms 173884 KB Output is correct
32 Correct 5229 ms 173924 KB Output is correct
33 Correct 1779 ms 142700 KB Output is correct
34 Correct 5804 ms 143156 KB Output is correct
35 Correct 1772 ms 142664 KB Output is correct
36 Correct 5849 ms 143188 KB Output is correct
37 Correct 1636 ms 174392 KB Output is correct
38 Correct 5393 ms 174532 KB Output is correct
39 Correct 2 ms 1868 KB Output is correct
40 Correct 5996 ms 143148 KB Output is correct