oj.uz

Submission #433541

# Submission time Handle Problem Language Result Execution time Memory
433541 2021-06-20T05:37:03 Z nvmdava Wombats (IOI13_wombats) C++17
100 / 100
 5714 ms 184968 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

const int SZ = 10;
int h[5001][201], v[5001][201];
int st[1024][201][201];
int r, c;

int opt[201];

void update(int id, int le, int ri, int L, int R){
	if(ri < L || le > R) return;
	if(le == ri){
		memset(st[id], 0x3f, sizeof st[id]);
		for(int i = 0; i < c; ++i){
			st[id][i][i] = 0;
			for(int k = le * SZ; k < min((le + 1) * SZ, r); ++k){
				for(int j = 1; j < c; ++j)
					st[id][i][j] = min(st[id][i][j], st[id][i][j - 1] + h[k][j - 1]);
				for(int j = c - 2; j >= 0; --j)
					st[id][i][j] = min(st[id][i][j], st[id][i][j + 1] + h[k][j]);
				for(int j = 0; j < c; ++j)
					st[id][i][j] += v[k][j];
			}
		}
		return;
	}
	int m = (le + ri) >> 1;
	update(id << 1, le, m, L, R);
	update(id << 1 | 1, m + 1, ri, L, R);
	memset(opt, 0, sizeof opt);
	opt[c] = c - 1;

	for(int i = 0; i < c; ++i){
		for(int j = c - 1; j >= 0; --j){
			pair<int, int> mn = {INT_MAX, 0};
			for(int k = opt[j]; k <= opt[j + 1]; ++k)
				mn = min(mn, {st[id << 1][i][k] + st[id << 1 | 1][k][j], -k});
			opt[j] = -mn.second;
			st[id][i][j] = mn.first;
		}
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r = R; c = C;

    for(int i = 0; i < R - 1; ++i)
    	for(int j = 0; j < C; ++j)
    		v[i][j] = V[i][j];
    for(int i = 0; i < R; ++i)
    	for(int j = 0; j < C - 1; ++j)
    		h[i][j] = H[i][j];

    update(1, 0, (r - 1) / SZ, 0, (r - 1) / SZ);
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    update(1, 0, (r - 1) / SZ, P / SZ, P / SZ);
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    update(1, 0, (r - 1) / SZ, P / SZ, P / SZ);
}

int escape(int V1, int V2) {
    return st[1][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 59 ms 89492 KB Output is correct
2 Correct 62 ms 89392 KB Output is correct
3 Correct 139 ms 92136 KB Output is correct
4 Correct 61 ms 89348 KB Output is correct
5 Correct 58 ms 89412 KB Output is correct
6 Correct 1 ms 564 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 432 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 83 ms 1712 KB Output is correct
12 Correct 1 ms 716 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 2960 KB Output is correct
2 Correct 139 ms 2948 KB Output is correct
3 Correct 140 ms 2960 KB Output is correct
4 Correct 146 ms 2964 KB Output is correct
5 Correct 144 ms 2892 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 604 ms 3044 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 97552 KB Output is correct
2 Correct 66 ms 97616 KB Output is correct
3 Correct 76 ms 97604 KB Output is correct
4 Correct 118 ms 99080 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 2956 KB Output is correct
2 Correct 128 ms 2844 KB Output is correct
3 Correct 142 ms 2856 KB Output is correct
4 Correct 140 ms 2972 KB Output is correct
5 Correct 138 ms 2892 KB Output is correct
6 Correct 66 ms 97608 KB Output is correct
7 Correct 62 ms 97632 KB Output is correct
8 Correct 68 ms 97588 KB Output is correct
9 Correct 106 ms 99072 KB Output is correct
10 Correct 57 ms 89416 KB Output is correct
11 Correct 59 ms 89412 KB Output is correct
12 Correct 135 ms 92184 KB Output is correct
13 Correct 64 ms 89412 KB Output is correct
14 Correct 59 ms 89412 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 716 KB Output is correct
19 Correct 1 ms 716 KB Output is correct
20 Correct 1 ms 716 KB Output is correct
21 Correct 2 ms 716 KB Output is correct
22 Correct 2 ms 716 KB Output is correct
23 Correct 1 ms 716 KB Output is correct
24 Correct 1 ms 692 KB Output is correct
25 Correct 81 ms 3092 KB Output is correct
26 Correct 1 ms 716 KB Output is correct
27 Correct 587 ms 3032 KB Output is correct
28 Correct 1466 ms 140644 KB Output is correct
29 Correct 1396 ms 116108 KB Output is correct
30 Correct 1420 ms 116100 KB Output is correct
31 Correct 1543 ms 142060 KB Output is correct
32 Correct 1 ms 460 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 2948 KB Output is correct
2 Correct 131 ms 2952 KB Output is correct
3 Correct 138 ms 2960 KB Output is correct
4 Correct 137 ms 2968 KB Output is correct
5 Correct 139 ms 2956 KB Output is correct
6 Correct 63 ms 97636 KB Output is correct
7 Correct 62 ms 97656 KB Output is correct
8 Correct 65 ms 97696 KB Output is correct
9 Correct 104 ms 98968 KB Output is correct
10 Correct 56 ms 89412 KB Output is correct
11 Correct 56 ms 89356 KB Output is correct
12 Correct 135 ms 92100 KB Output is correct
13 Correct 58 ms 89368 KB Output is correct
14 Correct 55 ms 89424 KB Output is correct
15 Correct 2286 ms 183844 KB Output is correct
16 Correct 5714 ms 184968 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 432 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 692 KB Output is correct
21 Correct 1 ms 696 KB Output is correct
22 Correct 1 ms 716 KB Output is correct
23 Correct 1 ms 716 KB Output is correct
24 Correct 1 ms 716 KB Output is correct
25 Correct 1 ms 716 KB Output is correct
26 Correct 1 ms 716 KB Output is correct
27 Correct 80 ms 3080 KB Output is correct
28 Correct 1 ms 716 KB Output is correct
29 Correct 608 ms 3036 KB Output is correct
30 Correct 1444 ms 140424 KB Output is correct
31 Correct 5302 ms 182536 KB Output is correct
32 Correct 5340 ms 182356 KB Output is correct
33 Correct 1412 ms 116228 KB Output is correct
34 Correct 5254 ms 151084 KB Output is correct
35 Correct 1430 ms 116000 KB Output is correct
36 Correct 5170 ms 151036 KB Output is correct
37 Correct 1530 ms 142164 KB Output is correct
38 Correct 5379 ms 183032 KB Output is correct
39 Correct 1 ms 460 KB Output is correct
40 Correct 5346 ms 151192 KB Output is correct