oj.uz

Submission #286574

# Submission time Handle Problem Language Result Execution time Memory
286574 2020-08-30T14:46:18 Z evpipis Wombats (IOI13_wombats) C++11
76 / 100
 20000 ms 32168 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

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

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 buck[75], root, temp;
    int opt[len_m][len_m];

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

        for (int i = 0; i < m; i++)
            for (int j = (i==0?0:opt[i-1][i-1]); 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][i] = j;
        for (int sz = 2; sz <= m; sz++){
            for (int a = 0; a < m; a++){
                int b = a+sz-1;
                if (b < m)
                    for (int c = opt[a][b-1]; c <= opt[a+1][b]; 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][b] = c;

                b = a-sz+1;
                if (b >= 0)
                    for (int c = opt[a][b+1]; c >= opt[a-1][b]; 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][b] = c;
            }
            /*
            for (int a = 0, b = sz-1; b < m; a++, b++)
                for (int c = opt[a][b-1]; c <= opt[a+1][b]; 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][b] = c;

            for (int b = 0, a = sz-1; a < m; a++, b++)
                for (int c = opt[a][b+1]; c >= opt[a-1][b]; 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][b] = c;
            */
        }

        return res;
    }

    void upd_buck(int b){
        int st = b*k, en = min(n, (b+1)*k);

        buck[b] = node(st);
        for (int i = st+1; i < en; i++)
            temp = node(i), buck[b] = join(buck[b], temp);
    }

    void upd_root(){
        root = buck[0];
        for (int b = 1; b*k < n; b++)
            root = join(root, buck[b]);
    }

    int ask(int a, int b){
        return root.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 = sqrt(n);
    for (int b = 0; k*b < n; b++)
        data.upd_buck(b);
    data.upd_root();
}

void changeH(int P, int Q, int W) {
    hor[P][Q] = W;
    data.upd_buck(P/k);
    data.upd_root();
}

void changeV(int P, int Q, int W) {
    ver[P][Q] = W;
    data.upd_buck(P/k);
    data.upd_root();
}

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_buck(int)':
wombats.cpp:79:18: warning: '<anonymous>' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |             temp = node(i), buck[b] = join(buck[b], temp);
      |             ~~~~~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1385 ms 20472 KB Output is correct
2 Correct 1403 ms 20532 KB Output is correct
3 Correct 1492 ms 23300 KB Output is correct
4 Correct 1396 ms 20536 KB Output is correct
5 Correct 1393 ms 20528 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 1 ms 896 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 2 ms 1664 KB Output is correct
5 Correct 2 ms 1664 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 3 ms 1664 KB Output is correct
8 Correct 3 ms 1664 KB Output is correct
9 Correct 2 ms 1664 KB Output is correct
10 Correct 2 ms 1664 KB Output is correct
11 Correct 89 ms 3960 KB Output is correct
12 Correct 2 ms 1664 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 3268 KB Output is correct
2 Correct 237 ms 3320 KB Output is correct
3 Correct 334 ms 3192 KB Output is correct
4 Correct 330 ms 3192 KB Output is correct
5 Correct 328 ms 3192 KB Output is correct
6 Correct 1 ms 896 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 1 ms 896 KB Output is correct
9 Correct 1080 ms 3100 KB Output is correct
10 Correct 1 ms 1024 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1389 ms 28536 KB Output is correct
2 Correct 1387 ms 28536 KB Output is correct
3 Correct 1416 ms 28600 KB Output is correct
4 Correct 1439 ms 29944 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 3320 KB Output is correct
2 Correct 242 ms 3200 KB Output is correct
3 Correct 329 ms 3068 KB Output is correct
4 Correct 334 ms 3104 KB Output is correct
5 Correct 333 ms 3192 KB Output is correct
6 Correct 1371 ms 28536 KB Output is correct
7 Correct 1383 ms 28492 KB Output is correct
8 Correct 1392 ms 28536 KB Output is correct
9 Correct 1428 ms 30216 KB Output is correct
10 Correct 1446 ms 20600 KB Output is correct
11 Correct 1369 ms 20600 KB Output is correct
12 Correct 1465 ms 23416 KB Output is correct
13 Correct 1385 ms 20600 KB Output is correct
14 Correct 1367 ms 20600 KB Output is correct
15 Correct 1 ms 896 KB Output is correct
16 Correct 1 ms 896 KB Output is correct
17 Correct 1 ms 896 KB Output is correct
18 Correct 2 ms 1664 KB Output is correct
19 Correct 3 ms 1664 KB Output is correct
20 Correct 2 ms 1664 KB Output is correct
21 Correct 3 ms 1664 KB Output is correct
22 Correct 2 ms 1664 KB Output is correct
23 Correct 2 ms 1664 KB Output is correct
24 Correct 3 ms 1696 KB Output is correct
25 Correct 89 ms 4088 KB Output is correct
26 Correct 3 ms 1664 KB Output is correct
27 Correct 1065 ms 3192 KB Output is correct
28 Correct 9105 ms 30684 KB Output is correct
29 Correct 11622 ms 26616 KB Output is correct
30 Correct 11865 ms 26920 KB Output is correct
31 Correct 8894 ms 32168 KB Output is correct
32 Correct 1 ms 1024 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 3388 KB Output is correct
2 Correct 238 ms 3256 KB Output is correct
3 Correct 326 ms 3072 KB Output is correct
4 Correct 330 ms 3192 KB Output is correct
5 Correct 320 ms 3064 KB Output is correct
6 Correct 1360 ms 28408 KB Output is correct
7 Correct 1371 ms 28536 KB Output is correct
8 Correct 1386 ms 28536 KB Output is correct
9 Correct 1461 ms 29308 KB Output is correct
10 Correct 1372 ms 20728 KB Output is correct
11 Correct 1367 ms 20576 KB Output is correct
12 Correct 1437 ms 22136 KB Output is correct
13 Correct 1379 ms 20472 KB Output is correct
14 Correct 1394 ms 20572 KB Output is correct
15 Correct 2989 ms 29160 KB Output is correct
16 Execution timed out 20011 ms 30072 KB Time limit exceeded
17 Halted 0 ms 0 KB -