oj.uz

Submission #104371

# Submission time Handle Problem Language Result Execution time Memory
104371 2019-04-05T17:44:13 Z ihdignite Wombats (IOI13_wombats) C++14
100 / 100
 7684 ms 95864 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

const int r=5e3, c=200, bs=20, bc=r/bs, sts=512;
int h[r][c-1], v[r][c], st[sts][c][c];

void solve(int a[c], int (*b)[c], int d[c], int l1=0, int r1=c-1, int l2=0, int r2=c-1) {
	if(l1>r1)
		return;
	int m1=(l1+r1)/2, m2=r2;
	for(int i=l2; i<=r2; ++i) {
		if(a[i]+b[i][m1]<=d[m1]) {
			d[m1]=a[i]+b[i][m1];
			m2=i;
		}
	}
	solve(a, b, d, l1, m1-1, l2, m2);
	solve(a, b, d, m1+1, r1, m2, r2);
}

void cs(int i, int l2, int r2) {
	memset(st[i], 0x3f, sizeof(st[i]));
	for(int j=0; j<c; ++j) {
		st[i][j][j]=0;
		for(int k=l2*bs; k<(l2+1)*bs; ++k) {
			for(int l=1; l<c; ++l)
				st[i][j][l]=min(st[i][j][l-1]+h[k][l-1], st[i][j][l]);
			for(int l=c-1; l; --l)
				st[i][j][l-1]=min(st[i][j][l]+h[k][l-1], st[i][j][l-1]);
			for(int l=0; l<c; ++l)
				st[i][j][l]+=v[k][l];
		}
	}
}

void cmb(int i) {
	memset(st[i], 0x3f, sizeof(st[i]));
	for(int j=0; j<c; ++j)
		solve(st[2*i][j], st[2*i+1], st[i][j]);
}

void upd(int l1, int r1, int i=1, int l2=0, int r2=bc-1) {
	if(l2==r2) {
		cs(i, l2, r2);
		return;
	}
	int m2=(l2+r2)/2;
	if(l1<=m2)
		upd(l1, r1, 2*i, l2, m2);
	if(m2<r1)
		upd(l1, r1, 2*i+1, m2+1, r2);
	cmb(i);
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
	memset(::h, 0x3f, sizeof(::h));
	for(int i=0; i<r; ++i)
		for(int j=0; j<c-1; ++j)
			::h[i][j]=h[i][j];
	for(int i=0; i<r-1; ++i)
		for(int j=0; j<c; ++j)
			::v[i][j]=v[i][j];
	upd(0, bc-1);
}

void changeH(int p, int q, int w) {
	h[p][q]=w;
	upd(p/bs, p/bs);
}

void changeV(int p, int q, int w) {
	v[p][q]=w;
	upd(p/bs, p/bs);
}

int escape(int a, int b) {
	return st[1][a][b];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
wombats.cpp: In function 'void cs(int, int, int)':
wombats.cpp:79:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:79:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:79:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:22:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 void cs(int i, int l2, int r2) {
      ^~
wombats.cpp:22:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:22:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6359 ms 90304 KB Output is correct
2 Correct 6365 ms 90236 KB Output is correct
3 Correct 6587 ms 91772 KB Output is correct
4 Correct 6972 ms 90240 KB Output is correct
5 Correct 6617 ms 90244 KB Output is correct
6 Correct 1217 ms 82424 KB Output is correct
7 Correct 1301 ms 82404 KB Output is correct
8 Correct 1280 ms 82552 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1332 ms 82448 KB Output is correct
2 Correct 1271 ms 82552 KB Output is correct
3 Correct 1258 ms 82548 KB Output is correct
4 Correct 1287 ms 82672 KB Output is correct
5 Correct 1367 ms 82492 KB Output is correct
6 Correct 1235 ms 82552 KB Output is correct
7 Correct 1288 ms 82620 KB Output is correct
8 Correct 1222 ms 82480 KB Output is correct
9 Correct 1253 ms 82568 KB Output is correct
10 Correct 1317 ms 82412 KB Output is correct
11 Correct 1417 ms 83576 KB Output is correct
12 Correct 1328 ms 82552 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2292 ms 82784 KB Output is correct
2 Correct 2362 ms 82920 KB Output is correct
3 Correct 2305 ms 82836 KB Output is correct
4 Correct 2214 ms 82752 KB Output is correct
5 Correct 2362 ms 82676 KB Output is correct
6 Correct 1288 ms 82496 KB Output is correct
7 Correct 1330 ms 82424 KB Output is correct
8 Correct 1314 ms 82620 KB Output is correct
9 Correct 6186 ms 82740 KB Output is correct
10 Correct 1307 ms 82552 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6719 ms 94292 KB Output is correct
2 Correct 6388 ms 94204 KB Output is correct
3 Correct 6549 ms 94200 KB Output is correct
4 Correct 6557 ms 95100 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2126 ms 82796 KB Output is correct
2 Correct 2277 ms 82808 KB Output is correct
3 Correct 2224 ms 82792 KB Output is correct
4 Correct 2280 ms 82796 KB Output is correct
5 Correct 2347 ms 82808 KB Output is correct
6 Correct 6535 ms 94340 KB Output is correct
7 Correct 6849 ms 94304 KB Output is correct
8 Correct 6756 ms 94072 KB Output is correct
9 Correct 7054 ms 95180 KB Output is correct
10 Correct 6563 ms 90256 KB Output is correct
11 Correct 6672 ms 90392 KB Output is correct
12 Correct 6773 ms 91716 KB Output is correct
13 Correct 6628 ms 90264 KB Output is correct
14 Correct 6897 ms 90232 KB Output is correct
15 Correct 1226 ms 82356 KB Output is correct
16 Correct 1224 ms 82340 KB Output is correct
17 Correct 1292 ms 82364 KB Output is correct
18 Correct 1217 ms 82376 KB Output is correct
19 Correct 1208 ms 82516 KB Output is correct
20 Correct 1242 ms 82468 KB Output is correct
21 Correct 1183 ms 82500 KB Output is correct
22 Correct 1219 ms 82456 KB Output is correct
23 Correct 1235 ms 82428 KB Output is correct
24 Correct 1217 ms 82416 KB Output is correct
25 Correct 1396 ms 83492 KB Output is correct
26 Correct 1276 ms 82412 KB Output is correct
27 Correct 5942 ms 82664 KB Output is correct
28 Correct 6189 ms 94688 KB Output is correct
29 Correct 6375 ms 92700 KB Output is correct
30 Correct 6162 ms 92492 KB Output is correct
31 Correct 6352 ms 95592 KB Output is correct
32 Correct 1447 ms 82420 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2371 ms 82680 KB Output is correct
2 Correct 2110 ms 82652 KB Output is correct
3 Correct 2134 ms 82728 KB Output is correct
4 Correct 2105 ms 82568 KB Output is correct
5 Correct 2205 ms 82844 KB Output is correct
6 Correct 6292 ms 94160 KB Output is correct
7 Correct 6602 ms 94292 KB Output is correct
8 Correct 6469 ms 94300 KB Output is correct
9 Correct 6591 ms 94960 KB Output is correct
10 Correct 6865 ms 90296 KB Output is correct
11 Correct 6719 ms 90236 KB Output is correct
12 Correct 6741 ms 91780 KB Output is correct
13 Correct 6716 ms 90244 KB Output is correct
14 Correct 6481 ms 90236 KB Output is correct
15 Correct 1759 ms 94204 KB Output is correct
16 Correct 7064 ms 95864 KB Output is correct
17 Correct 1342 ms 82524 KB Output is correct
18 Correct 1263 ms 82384 KB Output is correct
19 Correct 1221 ms 82420 KB Output is correct
20 Correct 1197 ms 82564 KB Output is correct
21 Correct 1233 ms 82472 KB Output is correct
22 Correct 1214 ms 82380 KB Output is correct
23 Correct 1315 ms 82524 KB Output is correct
24 Correct 1228 ms 82392 KB Output is correct
25 Correct 1350 ms 82592 KB Output is correct
26 Correct 1197 ms 82492 KB Output is correct
27 Correct 1268 ms 83604 KB Output is correct
28 Correct 1240 ms 82612 KB Output is correct
29 Correct 5640 ms 82672 KB Output is correct
30 Correct 5980 ms 94620 KB Output is correct
31 Correct 6924 ms 94864 KB Output is correct
32 Correct 6574 ms 94920 KB Output is correct
33 Correct 6281 ms 92548 KB Output is correct
34 Correct 7037 ms 92900 KB Output is correct
35 Correct 6757 ms 92468 KB Output is correct
36 Correct 7231 ms 92920 KB Output is correct
37 Correct 6286 ms 95700 KB Output is correct
38 Correct 6536 ms 95636 KB Output is correct
39 Correct 1295 ms 82356 KB Output is correct
40 Correct 7684 ms 92908 KB Output is correct