oj.uz

Submission #104372

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

const int r=5e3, c=200, bs=40, bc=r/bs, sts=256;
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 8366 ms 51080 KB Output is correct
2 Correct 8432 ms 51096 KB Output is correct
3 Correct 8080 ms 52624 KB Output is correct
4 Correct 8211 ms 51164 KB Output is correct
5 Correct 8156 ms 51092 KB Output is correct
6 Correct 1181 ms 43232 KB Output is correct
7 Correct 1140 ms 43256 KB Output is correct
8 Correct 1215 ms 43384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1206 ms 43372 KB Output is correct
2 Correct 1178 ms 43240 KB Output is correct
3 Correct 1188 ms 43280 KB Output is correct
4 Correct 1130 ms 43216 KB Output is correct
5 Correct 1141 ms 43280 KB Output is correct
6 Correct 1093 ms 43352 KB Output is correct
7 Correct 1113 ms 43252 KB Output is correct
8 Correct 1082 ms 43228 KB Output is correct
9 Correct 1077 ms 43260 KB Output is correct
10 Correct 1087 ms 43296 KB Output is correct
11 Correct 1162 ms 44320 KB Output is correct
12 Correct 1083 ms 43308 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2484 ms 43500 KB Output is correct
2 Correct 2565 ms 43488 KB Output is correct
3 Correct 2315 ms 43612 KB Output is correct
4 Correct 2361 ms 43512 KB Output is correct
5 Correct 2665 ms 43508 KB Output is correct
6 Correct 1117 ms 43308 KB Output is correct
7 Correct 1085 ms 43260 KB Output is correct
8 Correct 1234 ms 43176 KB Output is correct
9 Correct 7734 ms 43516 KB Output is correct
10 Correct 1170 ms 43436 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8389 ms 54996 KB Output is correct
2 Correct 8241 ms 54996 KB Output is correct
3 Correct 7755 ms 55012 KB Output is correct
4 Correct 8058 ms 55972 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2408 ms 43568 KB Output is correct
2 Correct 2581 ms 43496 KB Output is correct
3 Correct 2493 ms 43504 KB Output is correct
4 Correct 2369 ms 43612 KB Output is correct
5 Correct 2554 ms 43516 KB Output is correct
6 Correct 8457 ms 54996 KB Output is correct
7 Correct 8064 ms 54996 KB Output is correct
8 Correct 8114 ms 55000 KB Output is correct
9 Correct 8031 ms 55856 KB Output is correct
10 Correct 8041 ms 51084 KB Output is correct
11 Correct 8191 ms 51088 KB Output is correct
12 Correct 8061 ms 52612 KB Output is correct
13 Correct 7837 ms 51100 KB Output is correct
14 Correct 7854 ms 51132 KB Output is correct
15 Correct 1271 ms 43152 KB Output is correct
16 Correct 1221 ms 43212 KB Output is correct
17 Correct 1178 ms 43272 KB Output is correct
18 Correct 1273 ms 43332 KB Output is correct
19 Correct 1235 ms 43292 KB Output is correct
20 Correct 1114 ms 43284 KB Output is correct
21 Correct 1087 ms 43316 KB Output is correct
22 Correct 1098 ms 43264 KB Output is correct
23 Correct 1215 ms 43380 KB Output is correct
24 Correct 1144 ms 43292 KB Output is correct
25 Correct 1257 ms 44252 KB Output is correct
26 Correct 1089 ms 43292 KB Output is correct
27 Correct 7661 ms 43512 KB Output is correct
28 Correct 8016 ms 55468 KB Output is correct
29 Correct 7560 ms 53452 KB Output is correct
30 Correct 7890 ms 53336 KB Output is correct
31 Correct 7986 ms 56524 KB Output is correct
32 Correct 1249 ms 43368 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2551 ms 43500 KB Output is correct
2 Correct 2970 ms 43512 KB Output is correct
3 Correct 2551 ms 43516 KB Output is correct
4 Correct 2407 ms 43592 KB Output is correct
5 Correct 2412 ms 43640 KB Output is correct
6 Correct 8189 ms 55036 KB Output is correct
7 Correct 8079 ms 54996 KB Output is correct
8 Correct 8077 ms 55064 KB Output is correct
9 Correct 8173 ms 55812 KB Output is correct
10 Correct 7767 ms 51088 KB Output is correct
11 Correct 8505 ms 51104 KB Output is correct
12 Correct 8260 ms 52616 KB Output is correct
13 Correct 8312 ms 51204 KB Output is correct
14 Correct 8183 ms 51080 KB Output is correct
15 Correct 1331 ms 54940 KB Output is correct
16 Correct 8588 ms 56656 KB Output is correct
17 Correct 1144 ms 43260 KB Output is correct
18 Correct 1127 ms 43308 KB Output is correct
19 Correct 1204 ms 43184 KB Output is correct
20 Correct 1185 ms 43384 KB Output is correct
21 Correct 1282 ms 43264 KB Output is correct
22 Correct 1176 ms 43384 KB Output is correct
23 Correct 1175 ms 43384 KB Output is correct
24 Correct 1119 ms 43476 KB Output is correct
25 Correct 1110 ms 43316 KB Output is correct
26 Correct 1094 ms 43380 KB Output is correct
27 Correct 1162 ms 44536 KB Output is correct
28 Correct 1104 ms 43356 KB Output is correct
29 Correct 7879 ms 43512 KB Output is correct
30 Correct 8564 ms 55284 KB Output is correct
31 Correct 8745 ms 55676 KB Output is correct
32 Correct 8283 ms 55824 KB Output is correct
33 Correct 7771 ms 53328 KB Output is correct
34 Correct 8542 ms 53852 KB Output is correct
35 Correct 7494 ms 53344 KB Output is correct
36 Correct 8944 ms 53700 KB Output is correct
37 Correct 7730 ms 56428 KB Output is correct
38 Correct 8206 ms 56444 KB Output is correct
39 Correct 1234 ms 43236 KB Output is correct
40 Correct 9131 ms 53644 KB Output is correct