oj.uz

답안 #104373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104373 2019-04-05T17:48:07 Z ihdignite 웜뱃 (IOI13_wombats) C++14
100 / 100
 7332 ms 95824 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 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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 6631 ms 90236 KB Output is correct
2 Correct 6419 ms 90232 KB Output is correct
3 Correct 6587 ms 91780 KB Output is correct
4 Correct 6409 ms 90344 KB Output is correct
5 Correct 6776 ms 90236 KB Output is correct
6 Correct 1371 ms 82332 KB Output is correct
7 Correct 1316 ms 82332 KB Output is correct
8 Correct 1335 ms 82524 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1297 ms 82536 KB Output is correct
2 Correct 1317 ms 82420 KB Output is correct
3 Correct 1308 ms 82516 KB Output is correct
4 Correct 1347 ms 82388 KB Output is correct
5 Correct 1420 ms 82532 KB Output is correct
6 Correct 1267 ms 82492 KB Output is correct
7 Correct 1269 ms 82476 KB Output is correct
8 Correct 1278 ms 82484 KB Output is correct
9 Correct 1251 ms 82428 KB Output is correct
10 Correct 1302 ms 82544 KB Output is correct
11 Correct 1340 ms 83400 KB Output is correct
12 Correct 1275 ms 82420 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2135 ms 82756 KB Output is correct
2 Correct 2163 ms 82668 KB Output is correct
3 Correct 2379 ms 82788 KB Output is correct
4 Correct 2141 ms 82660 KB Output is correct
5 Correct 2223 ms 82668 KB Output is correct
6 Correct 1281 ms 82336 KB Output is correct
7 Correct 1199 ms 82396 KB Output is correct
8 Correct 1221 ms 82524 KB Output is correct
9 Correct 6093 ms 82820 KB Output is correct
10 Correct 1250 ms 82416 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6599 ms 94156 KB Output is correct
2 Correct 6414 ms 94160 KB Output is correct
3 Correct 6565 ms 94160 KB Output is correct
4 Correct 6282 ms 94972 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2253 ms 82652 KB Output is correct
2 Correct 2380 ms 82788 KB Output is correct
3 Correct 2514 ms 82676 KB Output is correct
4 Correct 2317 ms 82688 KB Output is correct
5 Correct 2371 ms 82676 KB Output is correct
6 Correct 6845 ms 94176 KB Output is correct
7 Correct 6927 ms 94152 KB Output is correct
8 Correct 6761 ms 94156 KB Output is correct
9 Correct 7028 ms 95028 KB Output is correct
10 Correct 6526 ms 90240 KB Output is correct
11 Correct 6778 ms 90232 KB Output is correct
12 Correct 6857 ms 91788 KB Output is correct
13 Correct 7119 ms 90276 KB Output is correct
14 Correct 6575 ms 90296 KB Output is correct
15 Correct 1377 ms 82348 KB Output is correct
16 Correct 1248 ms 82424 KB Output is correct
17 Correct 1368 ms 82476 KB Output is correct
18 Correct 1276 ms 82444 KB Output is correct
19 Correct 1228 ms 82504 KB Output is correct
20 Correct 1273 ms 82468 KB Output is correct
21 Correct 1287 ms 82696 KB Output is correct
22 Correct 1408 ms 82656 KB Output is correct
23 Correct 1298 ms 82492 KB Output is correct
24 Correct 1222 ms 82560 KB Output is correct
25 Correct 1269 ms 83576 KB Output is correct
26 Correct 1210 ms 82540 KB Output is correct
27 Correct 5883 ms 82832 KB Output is correct
28 Correct 6272 ms 94640 KB Output is correct
29 Correct 5777 ms 92672 KB Output is correct
30 Correct 5833 ms 92488 KB Output is correct
31 Correct 6288 ms 95700 KB Output is correct
32 Correct 1291 ms 82440 KB Output is correct

Subtask #6
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2323 ms 82560 KB Output is correct
2 Correct 2273 ms 82808 KB Output is correct
3 Correct 2172 ms 82688 KB Output is correct
4 Correct 2235 ms 82708 KB Output is correct
5 Correct 2269 ms 82680 KB Output is correct
6 Correct 6767 ms 94280 KB Output is correct
7 Correct 6805 ms 94152 KB Output is correct
8 Correct 6659 ms 94156 KB Output is correct
9 Correct 6770 ms 95016 KB Output is correct
10 Correct 6752 ms 90392 KB Output is correct
11 Correct 6435 ms 90232 KB Output is correct
12 Correct 6919 ms 91776 KB Output is correct
13 Correct 6749 ms 90364 KB Output is correct
14 Correct 7120 ms 90268 KB Output is correct
15 Correct 1643 ms 94264 KB Output is correct
16 Correct 7312 ms 95788 KB Output is correct
17 Correct 1224 ms 82376 KB Output is correct
18 Correct 1231 ms 82328 KB Output is correct
19 Correct 1215 ms 82440 KB Output is correct
20 Correct 1313 ms 82424 KB Output is correct
21 Correct 1260 ms 82424 KB Output is correct
22 Correct 1382 ms 82468 KB Output is correct
23 Correct 1333 ms 82408 KB Output is correct
24 Correct 1234 ms 82360 KB Output is correct
25 Correct 1295 ms 82364 KB Output is correct
26 Correct 1275 ms 82488 KB Output is correct
27 Correct 1288 ms 83440 KB Output is correct
28 Correct 1258 ms 82360 KB Output is correct
29 Correct 5811 ms 82660 KB Output is correct
30 Correct 6153 ms 94568 KB Output is correct
31 Correct 6911 ms 94984 KB Output is correct
32 Correct 6373 ms 94936 KB Output is correct
33 Correct 6466 ms 92612 KB Output is correct
34 Correct 6899 ms 92960 KB Output is correct
35 Correct 6318 ms 92460 KB Output is correct
36 Correct 7106 ms 92928 KB Output is correct
37 Correct 5765 ms 95824 KB Output is correct
38 Correct 6610 ms 95576 KB Output is correct
39 Correct 1290 ms 82676 KB Output is correct
40 Correct 7332 ms 92932 KB Output is correct