oj.uz

Submission #784343

# Submission time Handle Problem Language Result Execution time Memory
784343 2023-07-16T03:25:35 Z qwerasdfzxcl Wombats (IOI13_wombats) C++17
100 / 100
 6576 ms 101144 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 2e9 + 100, FUCK = 20;

int (*H)[200], (*V)[200], n, m;
int sum[5000][200];
int b[202][202], c[202][202], opt[202][202];

inline int dist(int x, int i, int j){
    if (i<=j) return sum[x][j] - sum[x][i];
    return sum[x][i] - sum[x][j];
}

struct Node{
    int a[202][202];
    int s, e;

    Node(){}

    void init(int l, int r){
        s = l, e = r;
        for (int i=0;i<m;i++){
            for (int j=0;j<m;j++){
                a[i][j] = dist(l, i, j);
            }
        }

        for (int z=l+1;z<=r;z++){
            for (int i=0;i<m;i++){
                for (int j=0;j<m;j++){
                    b[i][j] = dist(z, i, j);
                }
            }

            for (int d=-m+1;d<=m-1;d++){
                for (int i=max(0, -d);i<min(m, m-d);i++){
                    int j = i+d;
                    assert(j>=0 && j<m);
                    c[i][j] = INF;

                    for (int k=((j==0)?0:opt[i][j-1]);k<=((i==m-1)?(m-1):opt[i+1][j]);k++){
                        if (c[i][j] > a[i][k] + b[k][j] + V[z-1][k]){
                            c[i][j] = a[i][k] + b[k][j] + V[z-1][k];
                            opt[i][j] = k;
                        }
                    }
                }
            }

            // for (int i=0;i<m;i++){
            //     for (int j=0;j<m;j++){
            //         c[i][j] = INF;
            //         for (int k=0;k<m;k++){
            //             c[i][j] = min(c[i][j], a[i][k] + b[k][j] + V[z-1][k]);
            //         }
            //     }
            // }

            for (int i=0;i<m;i++){
                for (int j=0;j<m;j++) a[i][j] = c[i][j];
            }
        }
    }

    void merge(const Node &L, const Node &R){
        s = L.s, e = R.e;

        for (int d=-m+1;d<=m-1;d++){
            for (int i=max(0, -d);i<min(m, m-d);i++){
                int j = i+d;
                assert(j>=0 && j<m);
                a[i][j] = INF;

                for (int k=((j==0)?0:opt[i][j-1]);k<=((i==m-1)?(m-1):opt[i+1][j]);k++){
                    if (a[i][j] > L.a[i][k] + R.a[k][j] + V[L.e][k]){
                        a[i][j] = L.a[i][k] + R.a[k][j] + V[L.e][k];
                        opt[i][j] = k;
                    }
                }
            }
        }
        // for (int i=0;i<m;i++){
        //     for (int j=0;j<m;j++){
        //         a[i][j] = INF;
        //         for (int k=0;k<m;k++){
        //             a[i][j] = min(a[i][j], L.a[i][k] + R.a[k][j] + V[L.e][k]);
        //         }
        //     }
        // }
    }
};

struct Seg{
    Node tree[5050 / FUCK * 4];

    void init(int i, int l, int r){
        if (l==r){
            tree[i].init(l*FUCK, min((l+1)*FUCK-1, n-1));
            return;
        }

        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i].merge(tree[i<<1], tree[i<<1|1]);
    }

    void update(int i, int l, int r, int p){
        if (r<p || p<l) return;
        if (l==r){
            tree[i].init(l*FUCK, min((l+1)*FUCK-1, n-1));
            return;
        }

        int m = (l+r)>>1;
        update(i<<1, l, m, p); update(i<<1|1, m+1, r, p);
        tree[i].merge(tree[i<<1], tree[i<<1|1]);
    }
}tree;

void initH(int x){
    for (int i=1;i<m;i++) sum[x][i] = sum[x][i-1] + H[x][i-1];
}

void init(int R, int C, int h[5000][200], int v[5000][200]) {
    n = R, m = C;
    H = h, V = v;
    for (int i=0;i<R;i++) initH(i);

    tree.init(1, 0, (n-1)/FUCK);
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    initH(P);

    tree.update(1, 0, (n-1)/FUCK, P/FUCK);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;

    tree.update(1, 0, (n-1)/FUCK, P/FUCK);
}

int escape(int V1, int V2) {
    return tree.tree[1].a[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 4 ms 6344 KB Output is correct
2 Correct 4 ms 6336 KB Output is correct
3 Correct 58 ms 8348 KB Output is correct
4 Correct 4 ms 6404 KB Output is correct
5 Correct 4 ms 6356 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 53 ms 1716 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 1616 KB Output is correct
2 Correct 154 ms 1596 KB Output is correct
3 Correct 213 ms 1616 KB Output is correct
4 Correct 232 ms 1608 KB Output is correct
5 Correct 205 ms 1620 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 753 ms 1636 KB Output is correct
10 Correct 1 ms 304 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14676 KB Output is correct
2 Correct 8 ms 14708 KB Output is correct
3 Correct 9 ms 14624 KB Output is correct
4 Correct 35 ms 15732 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 1612 KB Output is correct
2 Correct 147 ms 1616 KB Output is correct
3 Correct 217 ms 1620 KB Output is correct
4 Correct 206 ms 1620 KB Output is correct
5 Correct 209 ms 1620 KB Output is correct
6 Correct 9 ms 14676 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 8 ms 14652 KB Output is correct
9 Correct 36 ms 15764 KB Output is correct
10 Correct 4 ms 6332 KB Output is correct
11 Correct 4 ms 6356 KB Output is correct
12 Correct 55 ms 8280 KB Output is correct
13 Correct 4 ms 6356 KB Output is correct
14 Correct 4 ms 6356 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 53 ms 1740 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 750 ms 1616 KB Output is correct
28 Correct 1339 ms 54072 KB Output is correct
29 Correct 1680 ms 44624 KB Output is correct
30 Correct 1649 ms 44628 KB Output is correct
31 Correct 1458 ms 54964 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 1532 KB Output is correct
2 Correct 155 ms 1532 KB Output is correct
3 Correct 212 ms 1532 KB Output is correct
4 Correct 205 ms 1536 KB Output is correct
5 Correct 231 ms 1532 KB Output is correct
6 Correct 9 ms 14640 KB Output is correct
7 Correct 8 ms 14584 KB Output is correct
8 Correct 9 ms 14548 KB Output is correct
9 Correct 38 ms 15412 KB Output is correct
10 Correct 4 ms 6356 KB Output is correct
11 Correct 4 ms 6356 KB Output is correct
12 Correct 55 ms 8016 KB Output is correct
13 Correct 4 ms 6356 KB Output is correct
14 Correct 4 ms 6356 KB Output is correct
15 Correct 1605 ms 92216 KB Output is correct
16 Correct 6576 ms 94684 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 54 ms 2716 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 762 ms 1620 KB Output is correct
30 Correct 1343 ms 57676 KB Output is correct
31 Correct 5198 ms 100576 KB Output is correct
32 Correct 5308 ms 100588 KB Output is correct
33 Correct 1667 ms 48124 KB Output is correct
34 Correct 6109 ms 83852 KB Output is correct
35 Correct 1669 ms 48228 KB Output is correct
36 Correct 6279 ms 83768 KB Output is correct
37 Correct 1406 ms 59568 KB Output is correct
38 Correct 5558 ms 101144 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 6468 ms 83940 KB Output is correct