oj.uz

Submission #1068082

# Submission time Handle Problem Language Result Execution time Memory
1068082 2024-08-21T07:12:36 Z thinknoexit Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 12884 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5000;
const int M = 100;
int rc[N][M]; // cost from (i, j) -> (i+1, j)
int cc[N][M]; // cost from (i, j) -> (i, j+1)
int n, m;
struct A {
    vector<vector<int>> dis;
    int r;
    void init() {
        dis.assign(m, vector<int>(m, 1e9));
    }
    A operator + (const A& o) const {
        A res;
        res.init();
        for (int i = 0;i < m;i++) {
            for (int j = 0;j < m;j++) {
                for (int k = 0;k < m;k++) {
                    res.dis[i][j] = min(res.dis[i][j],
                        dis[i][k] + rc[r][k] + o.dis[k][j]);
                }
            }
        }
        res.r = o.r;
        return res;
    }
} now;
A cal(int r) {
    A now; now.init();
    vector<int> sum(m);
    sum[0] = 0;
    for (int i = 1;i < m;i++) {
        sum[i] = sum[i - 1] + cc[r][i - 1];
    }
    for (int i = 0;i < m;i++) {
        for (int j = i;j < m;j++) {
            now.dis[i][j] = now.dis[j][i] = sum[j] - sum[i];
        }
    }
    now.r = r;
    return now;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R, m = C;
    for (int i = 0;i < n - 1;i++) {
        for (int j = 0;j < m;j++) {
            rc[i][j] = V[i][j];
        }
    }
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m - 1;j++) {
            cc[i][j] = H[i][j];
        }
    }
    now = cal(0);
    for (int i = 1;i < n;i++) now = now + cal(i);
}

void changeH(int P, int Q, int W) {
    cc[P][Q] = W;
    now = cal(0);
    for (int i = 1;i < n;i++) {
        now = now + cal(i);
    }
}

void changeV(int P, int Q, int W) {
    rc[P][Q] = W;
    now = cal(0);
    for (int i = 1;i < n;i++) {
        now = now + cal(i);
    }
}

int escape(int V1, int V2) {
    return now.dis[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 253 ms 6236 KB Output is correct
2 Correct 253 ms 6232 KB Output is correct
3 Correct 276 ms 7848 KB Output is correct
4 Correct 239 ms 6316 KB Output is correct
5 Correct 238 ms 6236 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 39 ms 1340 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11646 ms 808 KB Output is correct
2 Correct 11330 ms 804 KB Output is correct
3 Correct 11793 ms 808 KB Output is correct
4 Correct 12221 ms 820 KB Output is correct
5 Correct 11393 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 408 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Execution timed out 20089 ms 800 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 12120 KB Output is correct
2 Correct 355 ms 12124 KB Output is correct
3 Correct 394 ms 12124 KB Output is correct
4 Correct 398 ms 12884 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12092 ms 808 KB Output is correct
2 Correct 11611 ms 804 KB Output is correct
3 Correct 11729 ms 816 KB Output is correct
4 Correct 11882 ms 604 KB Output is correct
5 Correct 11469 ms 604 KB Output is correct
6 Correct 374 ms 12124 KB Output is correct
7 Correct 392 ms 12372 KB Output is correct
8 Correct 403 ms 12124 KB Output is correct
9 Correct 408 ms 12740 KB Output is correct
10 Correct 250 ms 6236 KB Output is correct
11 Correct 248 ms 6300 KB Output is correct
12 Correct 325 ms 7840 KB Output is correct
13 Correct 240 ms 6236 KB Output is correct
14 Correct 272 ms 6488 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 39 ms 1352 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Execution timed out 20081 ms 604 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 11965 ms 808 KB Output is correct
2 Correct 11560 ms 808 KB Output is correct
3 Correct 11750 ms 604 KB Output is correct
4 Correct 12025 ms 808 KB Output is correct
5 Correct 11580 ms 604 KB Output is correct
6 Correct 362 ms 12124 KB Output is correct
7 Correct 352 ms 12156 KB Output is correct
8 Correct 366 ms 12120 KB Output is correct
9 Correct 389 ms 12736 KB Output is correct
10 Correct 239 ms 6232 KB Output is correct
11 Correct 246 ms 6296 KB Output is correct
12 Correct 278 ms 7840 KB Output is correct
13 Correct 244 ms 6236 KB Output is correct
14 Correct 240 ms 6232 KB Output is correct
15 Execution timed out 20044 ms 12648 KB Time limit exceeded
16 Halted 0 ms 0 KB -