oj.uz

Submission #108183

# Submission time Handle Problem Language Result Execution time Memory
108183 2019-04-28T00:15:47 Z ihdignite Wombats (IOI13_wombats) C++14
100 / 100
 5332 ms 97016 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], 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);
	memset(st[i], 0x3f, sizeof(st[i]));
	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:74:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:74:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:74: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 4449 ms 90544 KB Output is correct
2 Correct 4655 ms 90460 KB Output is correct
3 Correct 4696 ms 92972 KB Output is correct
4 Correct 4573 ms 90460 KB Output is correct
5 Correct 4557 ms 90488 KB Output is correct
6 Correct 1127 ms 82624 KB Output is correct
7 Correct 1119 ms 82680 KB Output is correct
8 Correct 1152 ms 82652 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 82572 KB Output is correct
2 Correct 1157 ms 82808 KB Output is correct
3 Correct 1076 ms 82552 KB Output is correct
4 Correct 1120 ms 82680 KB Output is correct
5 Correct 1141 ms 82784 KB Output is correct
6 Correct 1168 ms 82688 KB Output is correct
7 Correct 1124 ms 82692 KB Output is correct
8 Correct 1114 ms 82732 KB Output is correct
9 Correct 1174 ms 82644 KB Output is correct
10 Correct 1169 ms 82592 KB Output is correct
11 Correct 1144 ms 85112 KB Output is correct
12 Correct 1106 ms 82808 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1862 ms 82940 KB Output is correct
2 Correct 1808 ms 82932 KB Output is correct
3 Correct 1789 ms 83064 KB Output is correct
4 Correct 1845 ms 82944 KB Output is correct
5 Correct 1748 ms 82948 KB Output is correct
6 Correct 1073 ms 82680 KB Output is correct
7 Correct 1066 ms 82672 KB Output is correct
8 Correct 1096 ms 82548 KB Output is correct
9 Correct 4677 ms 82968 KB Output is correct
10 Correct 1274 ms 82608 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4333 ms 94348 KB Output is correct
2 Correct 4449 ms 94332 KB Output is correct
3 Correct 4643 ms 94348 KB Output is correct
4 Correct 4575 ms 95832 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1785 ms 83104 KB Output is correct
2 Correct 1817 ms 82936 KB Output is correct
3 Correct 1896 ms 82960 KB Output is correct
4 Correct 1810 ms 82936 KB Output is correct
5 Correct 1767 ms 83080 KB Output is correct
6 Correct 4490 ms 94464 KB Output is correct
7 Correct 4391 ms 94364 KB Output is correct
8 Correct 4572 ms 94468 KB Output is correct
9 Correct 4528 ms 95996 KB Output is correct
10 Correct 4639 ms 90408 KB Output is correct
11 Correct 4439 ms 90620 KB Output is correct
12 Correct 4359 ms 93176 KB Output is correct
13 Correct 4491 ms 90404 KB Output is correct
14 Correct 4655 ms 90492 KB Output is correct
15 Correct 1107 ms 82660 KB Output is correct
16 Correct 1089 ms 82628 KB Output is correct
17 Correct 1093 ms 82552 KB Output is correct
18 Correct 1075 ms 82680 KB Output is correct
19 Correct 1073 ms 82676 KB Output is correct
20 Correct 1100 ms 82624 KB Output is correct
21 Correct 1105 ms 82640 KB Output is correct
22 Correct 1149 ms 82640 KB Output is correct
23 Correct 1166 ms 82652 KB Output is correct
24 Correct 1118 ms 82676 KB Output is correct
25 Correct 1291 ms 84836 KB Output is correct
26 Correct 1135 ms 82680 KB Output is correct
27 Correct 4521 ms 82936 KB Output is correct
28 Correct 4624 ms 96016 KB Output is correct
29 Correct 4439 ms 93816 KB Output is correct
30 Correct 4900 ms 93864 KB Output is correct
31 Correct 4863 ms 96780 KB Output is correct
32 Correct 1102 ms 82720 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1762 ms 82916 KB Output is correct
2 Correct 1705 ms 82856 KB Output is correct
3 Correct 1850 ms 82900 KB Output is correct
4 Correct 1840 ms 83012 KB Output is correct
5 Correct 1876 ms 82968 KB Output is correct
6 Correct 4677 ms 94420 KB Output is correct
7 Correct 4759 ms 94268 KB Output is correct
8 Correct 4715 ms 94428 KB Output is correct
9 Correct 4614 ms 95992 KB Output is correct
10 Correct 4630 ms 90484 KB Output is correct
11 Correct 4508 ms 90408 KB Output is correct
12 Correct 4344 ms 93092 KB Output is correct
13 Correct 4581 ms 90332 KB Output is correct
14 Correct 4740 ms 90488 KB Output is correct
15 Correct 1425 ms 95540 KB Output is correct
16 Correct 4830 ms 97016 KB Output is correct
17 Correct 1137 ms 82676 KB Output is correct
18 Correct 1126 ms 82612 KB Output is correct
19 Correct 1137 ms 82676 KB Output is correct
20 Correct 1137 ms 82680 KB Output is correct
21 Correct 1166 ms 82824 KB Output is correct
22 Correct 1120 ms 82612 KB Output is correct
23 Correct 1204 ms 82768 KB Output is correct
24 Correct 1112 ms 82680 KB Output is correct
25 Correct 1142 ms 82808 KB Output is correct
26 Correct 1085 ms 82800 KB Output is correct
27 Correct 1182 ms 84728 KB Output is correct
28 Correct 1079 ms 82704 KB Output is correct
29 Correct 4700 ms 83184 KB Output is correct
30 Correct 4648 ms 95884 KB Output is correct
31 Correct 4695 ms 96272 KB Output is correct
32 Correct 4660 ms 96264 KB Output is correct
33 Correct 4930 ms 93832 KB Output is correct
34 Correct 4809 ms 94168 KB Output is correct
35 Correct 4835 ms 93824 KB Output is correct
36 Correct 4988 ms 94008 KB Output is correct
37 Correct 4987 ms 96828 KB Output is correct
38 Correct 4586 ms 96852 KB Output is correct
39 Correct 1138 ms 82644 KB Output is correct
40 Correct 5332 ms 94184 KB Output is correct