oj.uz

Submission #286635

# Submission time Handle Problem Language Result Execution time Memory
286635 2020-08-30T15:49:13 Z evpipis Wombats (IOI13_wombats) C++11
100 / 100
 14499 ms 69784 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

const int len_n = 5005, len_m = 205, inf = 1e9+10, k = 20;
int hor[len_n][len_m], ver[len_n][len_m], n, m;

struct{
    struct node{
        int to[len_m][len_m];

        node(){
            for (int a = 0; a < m; a++)
                for (int b = 0; b < m; b++)
                    to[a][b] = inf; // check this
        }

        node(int i){
            for (int a = 0, suma = 0; a < m; a++){
                for (int b = 0, dif = suma; b < m; b++){
                    to[a][b] = dif + ver[i][b];

                    if (b < a)
                        dif -= hor[i][b];
                    else
                        dif += hor[i][b];
                }

                suma += hor[i][a];
            }
        }
    };

    node lev1[len_n/k+5], lev2[len_n/(k*k)+5], lev3[1], temp;
    int opt[len_m][2];

    node join(node &fir, node &sec){
        node res;

        for (int i = 0; i < m; i++)
            for (int j = (i==0?0:opt[i-1][0]); j < m; j++)
                if (fir.to[i][j]+sec.to[j][i] < res.to[i][i])
                    res.to[i][i] = fir.to[i][j]+sec.to[j][i], opt[i][0] = opt[i][1] = j;
        for (int sz = 2; sz <= m; sz++){
            for (int a = 0, b = sz-1; b < m; a++, b++)
                for (int c = opt[a][0]; c <= opt[a+1][0]; c++)
                    if (fir.to[a][c]+sec.to[c][b] < res.to[a][b])
                        res.to[a][b] = fir.to[a][c]+sec.to[c][b], opt[a][0] = c;

            for (int b = 0, a = sz-1; a < m; a++, b++)
                for (int c = opt[a][1]; c >= opt[a-1][1]; c--)
                    if (fir.to[a][c]+sec.to[c][b] < res.to[a][b])
                        res.to[a][b] = fir.to[a][c]+sec.to[c][b], opt[a][1] = c;
        }

        return res;
    }

    void upd_lev1(int b){
        lev1[b] = node(b*k);
        for (int i = b*k+1; i < (b+1)*k && i < n; i++)
            temp = node(i), lev1[b] = join(lev1[b], temp);
    }

    void upd_lev2(int b){
        lev2[b] = lev1[b*k];
        for (int i = b*k+1; i < (b+1)*k && i*k < n; i++)
            lev2[b] = join(lev2[b], lev1[i]);
    }

    void upd_lev3(int b = 0){
        lev3[b] = lev2[b*k];
        for (int i = b*k+1; i < (b+1)*k && i*k*k < n; i++)
            lev3[b] = join(lev3[b], lev2[i]);
    }

    int ask(int a, int b){
        return lev3[0].to[a][b];
    }
} data;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R, m = C;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m-1; j++)
            hor[i][j] = H[i][j];
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < m; j++)
            ver[i][j] = V[i][j];

    // k = 20;
    for (int i = 0; i*k < n; i++)
        data.upd_lev1(i);
    for (int i = 0; i*k*k < n; i++)
        data.upd_lev2(i);
    for (int i = 0; i*k*k*k < n; i++)
        data.upd_lev3(i);
}

void changeH(int a, int b, int c) {
    hor[a][b] = c;
    data.upd_lev1(a/k);
    data.upd_lev2(a/(k*k));
    data.upd_lev3(a/(k*k*k));
}

void changeV(int a, int b, int c) {
    ver[a][b] = c;
    data.upd_lev1(a/k);
    data.upd_lev2(a/(k*k));
    data.upd_lev3(a/(k*k*k));
}

int escape(int V1, int V2) {
    return data.ask(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;
      |      ^~~
wombats.cpp: In function 'void<unnamed struct>::upd_lev1(int)':
wombats.cpp:62:18: warning: '<anonymous>' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |             temp = node(i), lev1[b] = join(lev1[b], temp);
      |             ~~~~~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 51832 KB Output is correct
2 Correct 587 ms 51832 KB Output is correct
3 Correct 670 ms 54652 KB Output is correct
4 Correct 595 ms 51832 KB Output is correct
5 Correct 594 ms 51992 KB Output is correct
6 Correct 1 ms 1024 KB Output is correct
7 Correct 1 ms 1024 KB Output is correct
8 Correct 1 ms 1024 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1024 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 2 ms 1152 KB Output is correct
7 Correct 4 ms 1152 KB Output is correct
8 Correct 2 ms 1152 KB Output is correct
9 Correct 2 ms 1152 KB Output is correct
10 Correct 2 ms 1152 KB Output is correct
11 Correct 90 ms 3448 KB Output is correct
12 Correct 2 ms 1152 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 2304 KB Output is correct
2 Correct 247 ms 2280 KB Output is correct
3 Correct 365 ms 2424 KB Output is correct
4 Correct 352 ms 2500 KB Output is correct
5 Correct 354 ms 2424 KB Output is correct
6 Correct 2 ms 1024 KB Output is correct
7 Correct 1 ms 1152 KB Output is correct
8 Correct 1 ms 1024 KB Output is correct
9 Correct 1134 ms 2432 KB Output is correct
10 Correct 2 ms 1152 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 59904 KB Output is correct
2 Correct 598 ms 59896 KB Output is correct
3 Correct 600 ms 59896 KB Output is correct
4 Correct 640 ms 61176 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 2424 KB Output is correct
2 Correct 248 ms 2304 KB Output is correct
3 Correct 354 ms 2424 KB Output is correct
4 Correct 354 ms 2304 KB Output is correct
5 Correct 350 ms 2432 KB Output is correct
6 Correct 599 ms 60152 KB Output is correct
7 Correct 605 ms 60024 KB Output is correct
8 Correct 602 ms 59972 KB Output is correct
9 Correct 650 ms 61476 KB Output is correct
10 Correct 596 ms 51960 KB Output is correct
11 Correct 582 ms 51944 KB Output is correct
12 Correct 667 ms 54648 KB Output is correct
13 Correct 586 ms 51960 KB Output is correct
14 Correct 592 ms 51984 KB Output is correct
15 Correct 1 ms 1024 KB Output is correct
16 Correct 1 ms 1020 KB Output is correct
17 Correct 1 ms 1024 KB Output is correct
18 Correct 2 ms 1152 KB Output is correct
19 Correct 2 ms 1152 KB Output is correct
20 Correct 2 ms 1152 KB Output is correct
21 Correct 2 ms 1152 KB Output is correct
22 Correct 2 ms 1152 KB Output is correct
23 Correct 2 ms 1152 KB Output is correct
24 Correct 2 ms 1148 KB Output is correct
25 Correct 90 ms 3448 KB Output is correct
26 Correct 2 ms 1152 KB Output is correct
27 Correct 1138 ms 2368 KB Output is correct
28 Correct 2720 ms 64360 KB Output is correct
29 Correct 3765 ms 53624 KB Output is correct
30 Correct 3748 ms 53496 KB Output is correct
31 Correct 2828 ms 66076 KB Output is correct
32 Correct 1 ms 1024 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 2424 KB Output is correct
2 Correct 248 ms 2424 KB Output is correct
3 Correct 354 ms 2304 KB Output is correct
4 Correct 353 ms 2424 KB Output is correct
5 Correct 350 ms 2424 KB Output is correct
6 Correct 587 ms 59896 KB Output is correct
7 Correct 607 ms 59896 KB Output is correct
8 Correct 606 ms 60112 KB Output is correct
9 Correct 646 ms 61304 KB Output is correct
10 Correct 595 ms 51936 KB Output is correct
11 Correct 580 ms 51960 KB Output is correct
12 Correct 666 ms 54776 KB Output is correct
13 Correct 594 ms 51960 KB Output is correct
14 Correct 591 ms 52088 KB Output is correct
15 Correct 2670 ms 63992 KB Output is correct
16 Correct 13972 ms 66468 KB Output is correct
17 Correct 1 ms 1152 KB Output is correct
18 Correct 1 ms 1024 KB Output is correct
19 Correct 1 ms 1024 KB Output is correct
20 Correct 2 ms 1152 KB Output is correct
21 Correct 2 ms 1152 KB Output is correct
22 Correct 2 ms 1152 KB Output is correct
23 Correct 2 ms 1152 KB Output is correct
24 Correct 2 ms 1152 KB Output is correct
25 Correct 2 ms 1152 KB Output is correct
26 Correct 2 ms 1152 KB Output is correct
27 Correct 88 ms 3576 KB Output is correct
28 Correct 2 ms 1152 KB Output is correct
29 Correct 1135 ms 2424 KB Output is correct
30 Correct 2660 ms 64284 KB Output is correct
31 Correct 9195 ms 69080 KB Output is correct
32 Correct 9365 ms 69104 KB Output is correct
33 Correct 3800 ms 53676 KB Output is correct
34 Correct 13023 ms 57848 KB Output is correct
35 Correct 3705 ms 53376 KB Output is correct
36 Correct 13364 ms 57796 KB Output is correct
37 Correct 2875 ms 66168 KB Output is correct
38 Correct 10221 ms 69784 KB Output is correct
39 Correct 1 ms 1024 KB Output is correct
40 Correct 14499 ms 57712 KB Output is correct