oj.uz

Submission #784331

# Submission time Handle Problem Language Result Execution time Memory
784331 2023-07-16T03:09:34 Z qwerasdfzxcl Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 57768 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];

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 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 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 6356 KB Output is correct
2 Correct 3 ms 6356 KB Output is correct
3 Correct 58 ms 8012 KB Output is correct
4 Correct 6 ms 6324 KB Output is correct
5 Correct 4 ms 6356 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 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 58 ms 1356 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 2360 ms 1560 KB Output is correct
2 Correct 2467 ms 1556 KB Output is correct
3 Correct 2477 ms 1524 KB Output is correct
4 Correct 2441 ms 1540 KB Output is correct
5 Correct 2463 ms 1532 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 12197 ms 1528 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14652 KB Output is correct
3 Correct 9 ms 14700 KB Output is correct
4 Correct 36 ms 15996 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2356 ms 1456 KB Output is correct
2 Correct 2462 ms 1516 KB Output is correct
3 Correct 2500 ms 1540 KB Output is correct
4 Correct 2461 ms 1536 KB Output is correct
5 Correct 2469 ms 1532 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14652 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 36 ms 15964 KB Output is correct
10 Correct 4 ms 6356 KB Output is correct
11 Correct 4 ms 6356 KB Output is correct
12 Correct 58 ms 9148 KB Output is correct
13 Correct 4 ms 6356 KB Output is correct
14 Correct 4 ms 6356 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 440 KB Output is correct
19 Correct 1 ms 440 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 436 KB Output is correct
22 Correct 1 ms 440 KB Output is correct
23 Correct 1 ms 440 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 59 ms 2768 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 12187 ms 1536 KB Output is correct
28 Execution timed out 20095 ms 57768 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2373 ms 1572 KB Output is correct
2 Correct 2446 ms 1620 KB Output is correct
3 Correct 2482 ms 1536 KB Output is correct
4 Correct 2455 ms 1540 KB Output is correct
5 Correct 2460 ms 1536 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 7 ms 14696 KB Output is correct
8 Correct 8 ms 14656 KB Output is correct
9 Correct 35 ms 15996 KB Output is correct
10 Correct 4 ms 6336 KB Output is correct
11 Correct 4 ms 6336 KB Output is correct
12 Correct 58 ms 9100 KB Output is correct
13 Correct 5 ms 6336 KB Output is correct
14 Correct 4 ms 6356 KB Output is correct
15 Execution timed out 20024 ms 56912 KB Time limit exceeded
16 Halted 0 ms 0 KB -