oj.uz

Submission #784039

# Submission time Handle Problem Language Result Execution time Memory
784039 2023-07-15T15:16:43 Z qwerasdfzxcl Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 13092 KB 
#include "wombats.h"
#include <bits/stdc++.h>

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

int (*H)[200], (*V)[200], n, m;
int sum[5000][200];

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], nxt[202][202];

    Node(){}

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

    void push(int x){
        for (int i=0;i<m;i++){
            for (int j=0;j<m;j++){
                nxt[i][j] = INF;
                for (int k=0;k<m;k++){
                    nxt[i][j] = min(nxt[i][j], a[i][k] + V[x-1][k] + dist(x, k, j));
                }
            }
        }

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

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

void solve(){
    ans.init();
    for (int i=1;i<n;i++) ans.push(i);
}

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);

    solve();
}

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

    solve();
}

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

    solve();
}

int escape(int V1, int V2) {
    return ans.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 18 ms 4228 KB Output is correct
2 Correct 18 ms 4240 KB Output is correct
3 Correct 68 ms 5800 KB Output is correct
4 Correct 18 ms 4180 KB Output is correct
5 Correct 18 ms 4180 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 0 ms 212 KB Output is correct
3 Correct 0 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 53 ms 1292 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13488 ms 704 KB Output is correct
2 Correct 12882 ms 700 KB Output is correct
3 Correct 13214 ms 696 KB Output is correct
4 Correct 13534 ms 708 KB Output is correct
5 Correct 13037 ms 704 KB Output is correct
6 Correct 1 ms 220 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Execution timed out 20043 ms 700 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 12052 KB Output is correct
2 Correct 52 ms 12116 KB Output is correct
3 Correct 50 ms 12036 KB Output is correct
4 Correct 79 ms 12772 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13245 ms 700 KB Output is correct
2 Correct 12731 ms 700 KB Output is correct
3 Correct 13239 ms 700 KB Output is correct
4 Correct 13272 ms 708 KB Output is correct
5 Correct 13359 ms 700 KB Output is correct
6 Correct 99 ms 12032 KB Output is correct
7 Correct 52 ms 12028 KB Output is correct
8 Correct 52 ms 11988 KB Output is correct
9 Correct 90 ms 12748 KB Output is correct
10 Correct 19 ms 4240 KB Output is correct
11 Correct 18 ms 4240 KB Output is correct
12 Correct 72 ms 5812 KB Output is correct
13 Correct 27 ms 4180 KB Output is correct
14 Correct 20 ms 4240 KB Output is correct
15 Correct 1 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 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 54 ms 1372 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Execution timed out 20051 ms 704 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13289 ms 784 KB Output is correct
2 Correct 12667 ms 768 KB Output is correct
3 Correct 13539 ms 788 KB Output is correct
4 Correct 13364 ms 788 KB Output is correct
5 Correct 12857 ms 776 KB Output is correct
6 Correct 51 ms 12116 KB Output is correct
7 Correct 51 ms 11988 KB Output is correct
8 Correct 51 ms 12084 KB Output is correct
9 Correct 78 ms 13092 KB Output is correct
10 Correct 18 ms 4180 KB Output is correct
11 Correct 24 ms 4260 KB Output is correct
12 Correct 70 ms 5996 KB Output is correct
13 Correct 18 ms 4180 KB Output is correct
14 Correct 18 ms 4160 KB Output is correct
15 Execution timed out 20096 ms 12712 KB Time limit exceeded
16 Halted 0 ms 0 KB -