oj.uz

Submission #784332

# Submission time Handle Problem Language Result Execution time Memory
784332 2023-07-16T03:11:26 Z qwerasdfzxcl Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 100772 KB 
#include "wombats.h"
#include <bits/stdc++.h>

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

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 8532 KB Output is correct
2 Correct 4 ms 8532 KB Output is correct
3 Correct 61 ms 10168 KB Output is correct
4 Correct 4 ms 8620 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 1 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 56 ms 1364 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1330 ms 2300 KB Output is correct
2 Correct 1414 ms 2280 KB Output is correct
3 Correct 1414 ms 2300 KB Output is correct
4 Correct 1403 ms 2296 KB Output is correct
5 Correct 1389 ms 2336 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 6707 ms 2300 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 12 ms 17108 KB Output is correct
2 Correct 9 ms 17108 KB Output is correct
3 Correct 9 ms 17136 KB Output is correct
4 Correct 39 ms 17984 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1330 ms 2336 KB Output is correct
2 Correct 1405 ms 2380 KB Output is correct
3 Correct 1417 ms 2296 KB Output is correct
4 Correct 1410 ms 2324 KB Output is correct
5 Correct 1393 ms 2280 KB Output is correct
6 Correct 10 ms 17236 KB Output is correct
7 Correct 10 ms 17220 KB Output is correct
8 Correct 9 ms 17108 KB Output is correct
9 Correct 36 ms 17912 KB Output is correct
10 Correct 4 ms 8532 KB Output is correct
11 Correct 4 ms 8532 KB Output is correct
12 Correct 60 ms 10148 KB Output is correct
13 Correct 4 ms 8532 KB Output is correct
14 Correct 5 ms 8532 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 56 ms 1364 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 6676 ms 2300 KB Output is correct
28 Correct 14971 ms 95556 KB Output is correct
29 Correct 13818 ms 82252 KB Output is correct
30 Correct 13746 ms 82224 KB Output is correct
31 Correct 14928 ms 100772 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1354 ms 2376 KB Output is correct
2 Correct 1413 ms 2352 KB Output is correct
3 Correct 1440 ms 2380 KB Output is correct
4 Correct 1423 ms 2420 KB Output is correct
5 Correct 1400 ms 2364 KB Output is correct
6 Correct 11 ms 17236 KB Output is correct
7 Correct 12 ms 17236 KB Output is correct
8 Correct 9 ms 17212 KB Output is correct
9 Correct 39 ms 18236 KB Output is correct
10 Correct 4 ms 8532 KB Output is correct
11 Correct 5 ms 8640 KB Output is correct
12 Correct 59 ms 10380 KB Output is correct
13 Correct 5 ms 8532 KB Output is correct
14 Correct 5 ms 8644 KB Output is correct
15 Execution timed out 20020 ms 87920 KB Time limit exceeded
16 Halted 0 ms 0 KB -