oj.uz

Submission #286553

# Submission time Handle Problem Language Result Execution time Memory
286553 2020-08-30T14:27:22 Z evpipis Wombats (IOI13_wombats) C++11
76 / 100
 20000 ms 39032 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;

    node join(node fir, node sec){
        node res;
        int opt[len_m][len_m];

        for (int i = 0; i < m; i++)
            for (int j = 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][i] = j;
        for (int sz = 2; sz <= m; sz++){
            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;
        }
        /*queue<tuple<int, int, int, int> > myq;
        for (int a = 0; a < m; a++){
            myq.push(make_tuple(0, m-1, 0, m-1));
            while (!myq.empty()){
                tuple<int, int, int, int> fron = myq.front();
                myq.pop();

                int l = get<0>(fron), r = get<1>(fron), o1 = get<2>(fron), o2 = get<3>(fron);
                int b = (l+r)/2, opt;
                for (int c = o1; c <= o2; 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 = c;

                if (l < b)
                    myq.push(make_tuple(l, b-1, o1, opt));
                if (b < r)
                    myq.push(make_tuple(b+1, r, opt, o2));
            }
        }*/

        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++)
            buck[b] = join(buck[b], node(i));
    }

    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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2939 ms 21116 KB Output is correct
2 Correct 2961 ms 21112 KB Output is correct
3 Correct 3020 ms 23800 KB Output is correct
4 Correct 2956 ms 20984 KB Output is correct
5 Correct 3002 ms 21112 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 1152 KB Output is correct
8 Correct 1 ms 1152 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 3 ms 2048 KB Output is correct
5 Correct 3 ms 2048 KB Output is correct
6 Correct 3 ms 2048 KB Output is correct
7 Correct 3 ms 2176 KB Output is correct
8 Correct 3 ms 2048 KB Output is correct
9 Correct 3 ms 2048 KB Output is correct
10 Correct 3 ms 2048 KB Output is correct
11 Correct 98 ms 4472 KB Output is correct
12 Correct 3 ms 2048 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 3740 KB Output is correct
2 Correct 218 ms 3704 KB Output is correct
3 Correct 298 ms 3320 KB Output is correct
4 Correct 297 ms 3448 KB Output is correct
5 Correct 289 ms 3328 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 1184 KB Output is correct
8 Correct 1 ms 1152 KB Output is correct
9 Correct 1052 ms 3436 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2940 ms 29176 KB Output is correct
2 Correct 2997 ms 29176 KB Output is correct
3 Correct 3007 ms 29048 KB Output is correct
4 Correct 3021 ms 30328 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 3584 KB Output is correct
2 Correct 226 ms 3584 KB Output is correct
3 Correct 303 ms 3432 KB Output is correct
4 Correct 317 ms 3328 KB Output is correct
5 Correct 308 ms 3432 KB Output is correct
6 Correct 3068 ms 29044 KB Output is correct
7 Correct 2983 ms 28920 KB Output is correct
8 Correct 3048 ms 28920 KB Output is correct
9 Correct 3035 ms 30328 KB Output is correct
10 Correct 3034 ms 20984 KB Output is correct
11 Correct 3001 ms 20984 KB Output is correct
12 Correct 3105 ms 23800 KB Output is correct
13 Correct 2995 ms 20984 KB Output is correct
14 Correct 2993 ms 20984 KB Output is correct
15 Correct 1 ms 1152 KB Output is correct
16 Correct 2 ms 1152 KB Output is correct
17 Correct 1 ms 1152 KB Output is correct
18 Correct 3 ms 2048 KB Output is correct
19 Correct 3 ms 2048 KB Output is correct
20 Correct 3 ms 2048 KB Output is correct
21 Correct 3 ms 2048 KB Output is correct
22 Correct 3 ms 2048 KB Output is correct
23 Correct 3 ms 2048 KB Output is correct
24 Correct 3 ms 2048 KB Output is correct
25 Correct 96 ms 4472 KB Output is correct
26 Correct 3 ms 2176 KB Output is correct
27 Correct 1041 ms 3440 KB Output is correct
28 Correct 8598 ms 33260 KB Output is correct
29 Correct 9738 ms 29160 KB Output is correct
30 Correct 9886 ms 29100 KB Output is correct
31 Correct 8766 ms 34936 KB Output is correct
32 Correct 2 ms 1408 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 3600 KB Output is correct
2 Correct 223 ms 3584 KB Output is correct
3 Correct 323 ms 3564 KB Output is correct
4 Correct 311 ms 3328 KB Output is correct
5 Correct 305 ms 3320 KB Output is correct
6 Correct 2988 ms 29108 KB Output is correct
7 Correct 2967 ms 28920 KB Output is correct
8 Correct 2967 ms 28920 KB Output is correct
9 Correct 3028 ms 30328 KB Output is correct
10 Correct 2990 ms 20984 KB Output is correct
11 Correct 2952 ms 20984 KB Output is correct
12 Correct 3039 ms 23816 KB Output is correct
13 Correct 2979 ms 20984 KB Output is correct
14 Correct 2979 ms 21112 KB Output is correct
15 Correct 2509 ms 35372 KB Output is correct
16 Execution timed out 20005 ms 39032 KB Time limit exceeded
17 Halted 0 ms 0 KB -