oj.uz

Submission #286462

# Submission time Handle Problem Language Result Execution time Memory
286462 2020-08-30T12:37:37 Z evpipis Wombats (IOI13_wombats) C++11
55 / 100
 20000 ms 37396 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;

        for (int a = 0; a < m; a++){
            queue<tuple<int, int, int, int> > myq;

            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 2868 ms 20984 KB Output is correct
2 Correct 2870 ms 21104 KB Output is correct
3 Correct 2953 ms 22524 KB Output is correct
4 Correct 2884 ms 20984 KB Output is correct
5 Correct 2877 ms 20984 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 4 ms 2208 KB Output is correct
5 Correct 3 ms 2176 KB Output is correct
6 Correct 3 ms 2176 KB Output is correct
7 Correct 3 ms 2176 KB Output is correct
8 Correct 3 ms 2176 KB Output is correct
9 Correct 3 ms 2176 KB Output is correct
10 Correct 3 ms 2176 KB Output is correct
11 Correct 100 ms 3192 KB Output is correct
12 Correct 3 ms 2176 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 859 ms 3704 KB Output is correct
2 Correct 690 ms 3704 KB Output is correct
3 Correct 852 ms 3444 KB Output is correct
4 Correct 860 ms 3320 KB Output is correct
5 Correct 875 ms 3320 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
9 Correct 3336 ms 3448 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 2929 ms 28928 KB Output is correct
2 Correct 2925 ms 28920 KB Output is correct
3 Correct 2942 ms 29032 KB Output is correct
4 Correct 3000 ms 29816 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 837 ms 3600 KB Output is correct
2 Correct 679 ms 3708 KB Output is correct
3 Correct 847 ms 3448 KB Output is correct
4 Correct 850 ms 3444 KB Output is correct
5 Correct 831 ms 3448 KB Output is correct
6 Correct 2905 ms 28920 KB Output is correct
7 Correct 2909 ms 28908 KB Output is correct
8 Correct 2901 ms 28920 KB Output is correct
9 Correct 2920 ms 30072 KB Output is correct
10 Correct 2910 ms 21112 KB Output is correct
11 Correct 2883 ms 21112 KB Output is correct
12 Correct 2958 ms 22652 KB Output is correct
13 Correct 2912 ms 21052 KB Output is correct
14 Correct 2920 ms 21112 KB Output is correct
15 Correct 1 ms 1152 KB Output is correct
16 Correct 1 ms 1152 KB Output is correct
17 Correct 1 ms 1152 KB Output is correct
18 Correct 3 ms 2176 KB Output is correct
19 Correct 3 ms 2176 KB Output is correct
20 Correct 3 ms 2176 KB Output is correct
21 Correct 3 ms 2176 KB Output is correct
22 Correct 3 ms 2176 KB Output is correct
23 Correct 3 ms 2176 KB Output is correct
24 Correct 3 ms 2176 KB Output is correct
25 Correct 89 ms 3064 KB Output is correct
26 Correct 3 ms 2176 KB Output is correct
27 Correct 3283 ms 3324 KB Output is correct
28 Execution timed out 20039 ms 29752 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 3704 KB Output is correct
2 Correct 663 ms 3576 KB Output is correct
3 Correct 836 ms 3320 KB Output is correct
4 Correct 840 ms 3320 KB Output is correct
5 Correct 830 ms 3320 KB Output is correct
6 Correct 2918 ms 28920 KB Output is correct
7 Correct 2881 ms 28920 KB Output is correct
8 Correct 2954 ms 28920 KB Output is correct
9 Correct 2929 ms 29624 KB Output is correct
10 Correct 2882 ms 21112 KB Output is correct
11 Correct 2837 ms 21112 KB Output is correct
12 Correct 2946 ms 22648 KB Output is correct
13 Correct 2899 ms 21112 KB Output is correct
14 Correct 2871 ms 21112 KB Output is correct
15 Correct 8188 ms 29548 KB Output is correct
16 Execution timed out 20094 ms 37396 KB Time limit exceeded
17 Halted 0 ms 0 KB -