oj.uz

Submission #108186

# Submission time Handle Problem Language Result Execution time Memory
108186 2019-04-28T00:30:30 Z ihdignite Wombats (IOI13_wombats) C++14
100 / 100
 4631 ms 174292 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

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

void upd(int l1, int r1, int i=1, int l2=0, int r2=bc-1) {
	if(l2==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];
			}
		}
		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);
	for(int j1=0; j1<c; ++j1) {
		array<int, 2> d{INT_MAX, 0};
		for(int k=0; k<c; ++k)
			d=min(array<int, 2>{st[2*i][j1][k]+st[2*i+1][k][j1], -k}, d);
		st[i][j1][j1]=d[0];
		o[j1][j1]=-d[1];
		for(int j2=j1-1; ~j2; --j2) {
			d={INT_MAX, 0};
			for(int k=o[j1-1][j2]; k<=o[j1][j2+1]; ++k)
				d=min(array<int, 2>{st[2*i][j1][k]+st[2*i+1][k][j2], -k}, d);
			st[i][j1][j2]=d[0];
			o[j1][j2]=-d[1];
			d={INT_MAX, 0};
			for(int k=o[j2][j1-1]; k<=o[j2+1][j1]; ++k)
				d=min(array<int, 2>{st[2*i][j2][k]+st[2*i+1][k][j1], -k}, d);
			st[i][j2][j1]=d[0];
			o[j2][j1]=-d[1];
		}
	}
}

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 upd(int, int, int, int, int)':
wombats.cpp:73:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:73:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:73:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:8:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 void upd(int l1, int r1, int i=1, int l2=0, int r2=bc-1) {
      ^~~
wombats.cpp:8:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:8: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 4131 ms 168764 KB Output is correct
2 Correct 4157 ms 168568 KB Output is correct
3 Correct 4384 ms 170320 KB Output is correct
4 Correct 4560 ms 168616 KB Output is correct
5 Correct 4209 ms 168656 KB Output is correct
6 Correct 1276 ms 160876 KB Output is correct
7 Correct 1348 ms 160844 KB Output is correct
8 Correct 1312 ms 160788 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1316 ms 160816 KB Output is correct
2 Correct 1302 ms 160728 KB Output is correct
3 Correct 1212 ms 160936 KB Output is correct
4 Correct 1216 ms 160864 KB Output is correct
5 Correct 1277 ms 160824 KB Output is correct
6 Correct 1236 ms 160900 KB Output is correct
7 Correct 1188 ms 160860 KB Output is correct
8 Correct 1200 ms 160880 KB Output is correct
9 Correct 1240 ms 161016 KB Output is correct
10 Correct 1244 ms 160888 KB Output is correct
11 Correct 1399 ms 161800 KB Output is correct
12 Correct 1314 ms 160936 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1860 ms 161212 KB Output is correct
2 Correct 1877 ms 161092 KB Output is correct
3 Correct 1865 ms 161084 KB Output is correct
4 Correct 1756 ms 161084 KB Output is correct
5 Correct 1770 ms 161092 KB Output is correct
6 Correct 1275 ms 160756 KB Output is correct
7 Correct 1266 ms 160836 KB Output is correct
8 Correct 1332 ms 160740 KB Output is correct
9 Correct 3887 ms 161088 KB Output is correct
10 Correct 1200 ms 160788 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3918 ms 172572 KB Output is correct
2 Correct 3945 ms 172696 KB Output is correct
3 Correct 4295 ms 172668 KB Output is correct
4 Correct 3922 ms 173584 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1746 ms 161040 KB Output is correct
2 Correct 1854 ms 161204 KB Output is correct
3 Correct 1880 ms 161248 KB Output is correct
4 Correct 1950 ms 161152 KB Output is correct
5 Correct 1953 ms 161388 KB Output is correct
6 Correct 4162 ms 172752 KB Output is correct
7 Correct 4351 ms 172844 KB Output is correct
8 Correct 4135 ms 172752 KB Output is correct
9 Correct 3912 ms 173752 KB Output is correct
10 Correct 3848 ms 168796 KB Output is correct
11 Correct 3905 ms 168684 KB Output is correct
12 Correct 4224 ms 170440 KB Output is correct
13 Correct 4275 ms 168684 KB Output is correct
14 Correct 4137 ms 168672 KB Output is correct
15 Correct 1254 ms 160844 KB Output is correct
16 Correct 1284 ms 160900 KB Output is correct
17 Correct 1380 ms 160832 KB Output is correct
18 Correct 1314 ms 160792 KB Output is correct
19 Correct 1402 ms 160892 KB Output is correct
20 Correct 1309 ms 161060 KB Output is correct
21 Correct 1375 ms 160896 KB Output is correct
22 Correct 1290 ms 160912 KB Output is correct
23 Correct 1393 ms 160968 KB Output is correct
24 Correct 1307 ms 160948 KB Output is correct
25 Correct 1347 ms 162036 KB Output is correct
26 Correct 1364 ms 160948 KB Output is correct
27 Correct 4482 ms 161180 KB Output is correct
28 Correct 4525 ms 173252 KB Output is correct
29 Correct 4515 ms 171152 KB Output is correct
30 Correct 3889 ms 171200 KB Output is correct
31 Correct 4275 ms 174176 KB Output is correct
32 Correct 1222 ms 160888 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1968 ms 161140 KB Output is correct
2 Correct 1770 ms 161236 KB Output is correct
3 Correct 1790 ms 161212 KB Output is correct
4 Correct 1792 ms 161156 KB Output is correct
5 Correct 1840 ms 161144 KB Output is correct
6 Correct 4402 ms 172572 KB Output is correct
7 Correct 4464 ms 172580 KB Output is correct
8 Correct 4111 ms 172720 KB Output is correct
9 Correct 4046 ms 173328 KB Output is correct
10 Correct 4108 ms 168708 KB Output is correct
11 Correct 4051 ms 168824 KB Output is correct
12 Correct 4323 ms 170260 KB Output is correct
13 Correct 4176 ms 168696 KB Output is correct
14 Correct 4033 ms 168736 KB Output is correct
15 Correct 1408 ms 172764 KB Output is correct
16 Correct 4137 ms 174292 KB Output is correct
17 Correct 1215 ms 160892 KB Output is correct
18 Correct 1204 ms 160760 KB Output is correct
19 Correct 1210 ms 160940 KB Output is correct
20 Correct 1196 ms 161064 KB Output is correct
21 Correct 1247 ms 161016 KB Output is correct
22 Correct 1211 ms 161144 KB Output is correct
23 Correct 1207 ms 161016 KB Output is correct
24 Correct 1216 ms 161016 KB Output is correct
25 Correct 1264 ms 161012 KB Output is correct
26 Correct 1287 ms 161084 KB Output is correct
27 Correct 1347 ms 162180 KB Output is correct
28 Correct 1303 ms 161148 KB Output is correct
29 Correct 3562 ms 161184 KB Output is correct
30 Correct 4403 ms 173060 KB Output is correct
31 Correct 4098 ms 173512 KB Output is correct
32 Correct 4251 ms 173428 KB Output is correct
33 Correct 4321 ms 170948 KB Output is correct
34 Correct 4415 ms 171440 KB Output is correct
35 Correct 4407 ms 171092 KB Output is correct
36 Correct 4219 ms 171376 KB Output is correct
37 Correct 4301 ms 173956 KB Output is correct
38 Correct 4424 ms 174004 KB Output is correct
39 Correct 1349 ms 161120 KB Output is correct
40 Correct 4631 ms 171312 KB Output is correct