oj.uz

Submission #108158

# Submission time Handle Problem Language Result Execution time Memory
108158 2019-04-27T18:36:09 Z ihdignite Wombats (IOI13_wombats) C++14
100 / 100
 7414 ms 105160 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;
	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 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);
	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 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:71:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:71:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:71:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp: In function 'void solve(int*, int (*)[200], int*, int, int, int, int)':
wombats.cpp:18:7: warning: 'm2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  solve(a, b, d, l1, m1-1, l2, m2);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void upd(int, int, int, int, int)':
wombats.cpp:22: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: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 5888 ms 90300 KB Output is correct
2 Correct 6329 ms 90360 KB Output is correct
3 Correct 6441 ms 91804 KB Output is correct
4 Correct 5956 ms 90364 KB Output is correct
5 Correct 5996 ms 90412 KB Output is correct
6 Correct 1215 ms 82636 KB Output is correct
7 Correct 1294 ms 82628 KB Output is correct
8 Correct 1189 ms 82456 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1363 ms 82588 KB Output is correct
2 Correct 1289 ms 82512 KB Output is correct
3 Correct 1274 ms 82552 KB Output is correct
4 Correct 1248 ms 82680 KB Output is correct
5 Correct 1270 ms 82572 KB Output is correct
6 Correct 1260 ms 82656 KB Output is correct
7 Correct 1223 ms 82616 KB Output is correct
8 Correct 1220 ms 82552 KB Output is correct
9 Correct 1270 ms 82552 KB Output is correct
10 Correct 1176 ms 82700 KB Output is correct
11 Correct 1240 ms 84828 KB Output is correct
12 Correct 1210 ms 82680 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2152 ms 82692 KB Output is correct
2 Correct 2058 ms 82824 KB Output is correct
3 Correct 2202 ms 82760 KB Output is correct
4 Correct 2294 ms 82992 KB Output is correct
5 Correct 2249 ms 82892 KB Output is correct
6 Correct 1250 ms 82468 KB Output is correct
7 Correct 1257 ms 82680 KB Output is correct
8 Correct 1300 ms 82780 KB Output is correct
9 Correct 6237 ms 82856 KB Output is correct
10 Correct 1262 ms 82340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6026 ms 94332 KB Output is correct
2 Correct 6022 ms 94196 KB Output is correct
3 Correct 6323 ms 94196 KB Output is correct
4 Correct 6446 ms 95096 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2201 ms 82872 KB Output is correct
2 Correct 2249 ms 82780 KB Output is correct
3 Correct 2334 ms 82936 KB Output is correct
4 Correct 2116 ms 82816 KB Output is correct
5 Correct 2184 ms 82760 KB Output is correct
6 Correct 5996 ms 94376 KB Output is correct
7 Correct 6387 ms 94288 KB Output is correct
8 Correct 6253 ms 94328 KB Output is correct
9 Correct 6459 ms 95824 KB Output is correct
10 Correct 6141 ms 90272 KB Output is correct
11 Correct 6059 ms 90452 KB Output is correct
12 Correct 6248 ms 93004 KB Output is correct
13 Correct 6156 ms 90316 KB Output is correct
14 Correct 6009 ms 90360 KB Output is correct
15 Correct 1282 ms 82524 KB Output is correct
16 Correct 1285 ms 82500 KB Output is correct
17 Correct 1267 ms 82532 KB Output is correct
18 Correct 1212 ms 82416 KB Output is correct
19 Correct 1254 ms 82356 KB Output is correct
20 Correct 1243 ms 82404 KB Output is correct
21 Correct 1259 ms 82380 KB Output is correct
22 Correct 1294 ms 82372 KB Output is correct
23 Correct 1289 ms 82456 KB Output is correct
24 Correct 1241 ms 82508 KB Output is correct
25 Correct 1270 ms 84848 KB Output is correct
26 Correct 1296 ms 82416 KB Output is correct
27 Correct 6138 ms 82752 KB Output is correct
28 Correct 6046 ms 98528 KB Output is correct
29 Correct 6258 ms 96172 KB Output is correct
30 Correct 6011 ms 95948 KB Output is correct
31 Correct 6425 ms 100104 KB Output is correct
32 Correct 1239 ms 82384 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2232 ms 82924 KB Output is correct
2 Correct 2297 ms 82684 KB Output is correct
3 Correct 2265 ms 82808 KB Output is correct
4 Correct 2308 ms 82788 KB Output is correct
5 Correct 2289 ms 82840 KB Output is correct
6 Correct 5984 ms 94328 KB Output is correct
7 Correct 6349 ms 94456 KB Output is correct
8 Correct 6349 ms 94356 KB Output is correct
9 Correct 6440 ms 95740 KB Output is correct
10 Correct 5978 ms 90304 KB Output is correct
11 Correct 5938 ms 90288 KB Output is correct
12 Correct 6210 ms 92928 KB Output is correct
13 Correct 6059 ms 90396 KB Output is correct
14 Correct 6117 ms 90176 KB Output is correct
15 Correct 1515 ms 104196 KB Output is correct
16 Correct 6835 ms 105160 KB Output is correct
17 Correct 1183 ms 82540 KB Output is correct
18 Correct 1303 ms 82524 KB Output is correct
19 Correct 1276 ms 82464 KB Output is correct
20 Correct 1257 ms 82636 KB Output is correct
21 Correct 1274 ms 82548 KB Output is correct
22 Correct 1162 ms 82508 KB Output is correct
23 Correct 1166 ms 82568 KB Output is correct
24 Correct 1173 ms 82436 KB Output is correct
25 Correct 1275 ms 82484 KB Output is correct
26 Correct 1252 ms 82448 KB Output is correct
27 Correct 1299 ms 84984 KB Output is correct
28 Correct 1323 ms 82624 KB Output is correct
29 Correct 5980 ms 82812 KB Output is correct
30 Correct 6524 ms 98520 KB Output is correct
31 Correct 7058 ms 102640 KB Output is correct
32 Correct 6620 ms 102592 KB Output is correct
33 Correct 6499 ms 96208 KB Output is correct
34 Correct 7149 ms 99896 KB Output is correct
35 Correct 6377 ms 96172 KB Output is correct
36 Correct 7086 ms 99804 KB Output is correct
37 Correct 6612 ms 100088 KB Output is correct
38 Correct 6606 ms 103320 KB Output is correct
39 Correct 1275 ms 82340 KB Output is correct
40 Correct 7414 ms 100120 KB Output is correct