oj.uz

Submission #199847

# Submission time Handle Problem Language Result Execution time Memory
199847 2020-02-03T18:02:29 Z dolphingarlic Wombats (IOI13_wombats) C++14
100 / 100
 9251 ms 184044 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

const int K = 10;

int R, C, H[5000][200], V[5000][200];

int T[1024][200][200];

void hsmooth(int* A, int r) {
    FOR(i, 1, C) A[i] = min(A[i], A[i - 1] + H[r][i - 1]);
    for (int i = C - 2; i >= 0; i--) A[i] = min(A[i], A[i + 1] + H[r][i]);
}

void bruteforce(int A[200][200], int rlo, int rhi) {
    FOR(i, 0, C) {
        int* B = A[i];
        FOR(j, 0, C) B[j] = i == j ? 0 : 0x3f3f3f3f;

        FOR(r, rlo, rhi) {
            hsmooth(B, r);
            FOR(j, 0, C) {
                B[j] += V[r][j];
            }
        }
    }
}

void solve(int i, int jlo, int jhi, int klo, int khi, int R[200], int X[200], int Y[200][200]) {
    if (jlo == jhi) return;

    int jmd = (jlo + jhi) / 2;
    int kmd = klo;

    R[jmd] = X[kmd] + Y[kmd][jmd];
    FOR(k, klo + 1, khi) {
        int v = X[k] + Y[k][jmd];
        if (v < R[jmd]) {
            R[jmd] = v;
            kmd = k;
        }
    }

    solve(i, jlo, jmd, klo, kmd + 1, R, X, Y);
    solve(i, jmd + 1, jhi, kmd, khi, R, X, Y);
}

void marge(int R[200][200], int X[200][200], int Y[200][200]) {
    FOR(i, 0, C) solve(i, 0, C, 0, C, R[i], X[i], Y);
}

void update(int x, int rlo, int rhi, int rupdate) {
    if (rlo + 1 >= R) return;
    if (rhi - rlo == K) bruteforce(T[x], rlo, min(R - 1, rhi));
    else {
        int rmd = (rlo + rhi) / 2;

        if (rupdate == -1 || rupdate < rmd) update(2 * x + 1, rlo, rmd, rupdate);
        if (rupdate == -1 || rmd <= rupdate) update(2 * x + 2, rmd, rhi, rupdate);

        if (rmd + 1 < R) marge(T[x], T[2 * x + 1], T[2 * x + 2]);
        else memcpy(T[x], T[2 * x + 1], sizeof(T[x]));
    }
}

void init(int RR, int CC, int HH[5000][200], int VV[5000][200]) {
    R = RR;
    C = CC;
    memcpy(H, HH, sizeof(H));
    memcpy(V, VV, sizeof(V));
    update(0, 0, 512 * K, -1);
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    update(0, 0, 512 * K, P);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    update(0, 0, 512 * K, P);
}

int escape(int V1, int V2) {
    hsmooth(T[0][V1], R - 1);
    return T[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]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16760 KB Output is correct
2 Correct 18 ms 16760 KB Output is correct
3 Correct 101 ms 19516 KB Output is correct
4 Correct 18 ms 16760 KB Output is correct
5 Correct 19 ms 16760 KB Output is correct
6 Correct 15 ms 9720 KB Output is correct
7 Correct 16 ms 9592 KB Output is correct
8 Correct 16 ms 9592 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9720 KB Output is correct
2 Correct 15 ms 9592 KB Output is correct
3 Correct 16 ms 9592 KB Output is correct
4 Correct 15 ms 9592 KB Output is correct
5 Correct 17 ms 9592 KB Output is correct
6 Correct 16 ms 9592 KB Output is correct
7 Correct 17 ms 9592 KB Output is correct
8 Correct 16 ms 9592 KB Output is correct
9 Correct 16 ms 9592 KB Output is correct
10 Correct 17 ms 9592 KB Output is correct
11 Correct 135 ms 12152 KB Output is correct
12 Correct 16 ms 9592 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 11128 KB Output is correct
2 Correct 182 ms 11128 KB Output is correct
3 Correct 224 ms 11316 KB Output is correct
4 Correct 217 ms 11128 KB Output is correct
5 Correct 217 ms 11128 KB Output is correct
6 Correct 15 ms 9592 KB Output is correct
7 Correct 16 ms 9592 KB Output is correct
8 Correct 16 ms 9596 KB Output is correct
9 Correct 853 ms 11256 KB Output is correct
10 Correct 15 ms 9592 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21368 KB Output is correct
2 Correct 22 ms 21496 KB Output is correct
3 Correct 22 ms 21368 KB Output is correct
4 Correct 71 ms 22904 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 11152 KB Output is correct
2 Correct 183 ms 11140 KB Output is correct
3 Correct 224 ms 11128 KB Output is correct
4 Correct 216 ms 11128 KB Output is correct
5 Correct 226 ms 11128 KB Output is correct
6 Correct 21 ms 21496 KB Output is correct
7 Correct 21 ms 21368 KB Output is correct
8 Correct 22 ms 21368 KB Output is correct
9 Correct 66 ms 22780 KB Output is correct
10 Correct 19 ms 16760 KB Output is correct
11 Correct 18 ms 16760 KB Output is correct
12 Correct 111 ms 19448 KB Output is correct
13 Correct 18 ms 16760 KB Output is correct
14 Correct 18 ms 16760 KB Output is correct
15 Correct 17 ms 9592 KB Output is correct
16 Correct 16 ms 9592 KB Output is correct
17 Correct 18 ms 9592 KB Output is correct
18 Correct 16 ms 9592 KB Output is correct
19 Correct 16 ms 9592 KB Output is correct
20 Correct 16 ms 9596 KB Output is correct
21 Correct 16 ms 9592 KB Output is correct
22 Correct 15 ms 9592 KB Output is correct
23 Correct 16 ms 9592 KB Output is correct
24 Correct 15 ms 9592 KB Output is correct
25 Correct 132 ms 11932 KB Output is correct
26 Correct 16 ms 9592 KB Output is correct
27 Correct 844 ms 11156 KB Output is correct
28 Correct 2012 ms 102616 KB Output is correct
29 Correct 2144 ms 86444 KB Output is correct
30 Correct 2132 ms 86520 KB Output is correct
31 Correct 2258 ms 104312 KB Output is correct
32 Correct 16 ms 9592 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 11128 KB Output is correct
2 Correct 189 ms 11148 KB Output is correct
3 Correct 229 ms 11132 KB Output is correct
4 Correct 225 ms 11164 KB Output is correct
5 Correct 220 ms 11132 KB Output is correct
6 Correct 37 ms 21368 KB Output is correct
7 Correct 30 ms 21372 KB Output is correct
8 Correct 30 ms 21368 KB Output is correct
9 Correct 88 ms 22776 KB Output is correct
10 Correct 22 ms 16760 KB Output is correct
11 Correct 20 ms 16760 KB Output is correct
12 Correct 118 ms 19508 KB Output is correct
13 Correct 21 ms 16760 KB Output is correct
14 Correct 20 ms 16796 KB Output is correct
15 Correct 2757 ms 182548 KB Output is correct
16 Correct 9251 ms 184044 KB Output is correct
17 Correct 16 ms 9592 KB Output is correct
18 Correct 17 ms 9592 KB Output is correct
19 Correct 16 ms 9592 KB Output is correct
20 Correct 16 ms 9592 KB Output is correct
21 Correct 16 ms 9592 KB Output is correct
22 Correct 17 ms 9592 KB Output is correct
23 Correct 16 ms 9592 KB Output is correct
24 Correct 17 ms 9592 KB Output is correct
25 Correct 17 ms 9592 KB Output is correct
26 Correct 17 ms 9592 KB Output is correct
27 Correct 133 ms 12024 KB Output is correct
28 Correct 18 ms 9592 KB Output is correct
29 Correct 848 ms 11132 KB Output is correct
30 Correct 2035 ms 102904 KB Output is correct
31 Correct 7506 ms 181428 KB Output is correct
32 Correct 7618 ms 181492 KB Output is correct
33 Correct 2173 ms 86520 KB Output is correct
34 Correct 8708 ms 151772 KB Output is correct
35 Correct 2172 ms 86520 KB Output is correct
36 Correct 8662 ms 151640 KB Output is correct
37 Correct 2261 ms 104260 KB Output is correct
38 Correct 8037 ms 182044 KB Output is correct
39 Correct 16 ms 9592 KB Output is correct
40 Correct 9156 ms 151780 KB Output is correct