oj.uz

Submission #108184

# Submission time Handle Problem Language Result Execution time Memory
108184 2019-04-28T00:24:10 Z ihdignite Wombats (IOI13_wombats) C++14
100 / 100
 4320 ms 175196 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);
	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 3664 ms 168908 KB Output is correct
2 Correct 3561 ms 168800 KB Output is correct
3 Correct 3679 ms 170476 KB Output is correct
4 Correct 3597 ms 168724 KB Output is correct
5 Correct 3622 ms 168756 KB Output is correct
6 Correct 1244 ms 160996 KB Output is correct
7 Correct 1200 ms 161048 KB Output is correct
8 Correct 1298 ms 161044 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1286 ms 160888 KB Output is correct
2 Correct 1270 ms 161012 KB Output is correct
3 Correct 1264 ms 161040 KB Output is correct
4 Correct 1274 ms 161016 KB Output is correct
5 Correct 1220 ms 161016 KB Output is correct
6 Correct 1210 ms 160920 KB Output is correct
7 Correct 1250 ms 160924 KB Output is correct
8 Correct 1292 ms 160956 KB Output is correct
9 Correct 1302 ms 160920 KB Output is correct
10 Correct 1308 ms 160992 KB Output is correct
11 Correct 1336 ms 162080 KB Output is correct
12 Correct 1280 ms 160964 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1736 ms 161224 KB Output is correct
2 Correct 1778 ms 161244 KB Output is correct
3 Correct 1912 ms 161244 KB Output is correct
4 Correct 1711 ms 161204 KB Output is correct
5 Correct 1685 ms 161104 KB Output is correct
6 Correct 1215 ms 160888 KB Output is correct
7 Correct 1270 ms 161040 KB Output is correct
8 Correct 1224 ms 160860 KB Output is correct
9 Correct 3828 ms 161264 KB Output is correct
10 Correct 1216 ms 161016 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3767 ms 172648 KB Output is correct
2 Correct 3733 ms 172792 KB Output is correct
3 Correct 4078 ms 172688 KB Output is correct
4 Correct 3982 ms 173600 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1842 ms 161172 KB Output is correct
2 Correct 1797 ms 161272 KB Output is correct
3 Correct 1851 ms 161232 KB Output is correct
4 Correct 1899 ms 161352 KB Output is correct
5 Correct 1720 ms 161272 KB Output is correct
6 Correct 3569 ms 172668 KB Output is correct
7 Correct 3993 ms 172644 KB Output is correct
8 Correct 3886 ms 172720 KB Output is correct
9 Correct 3623 ms 173684 KB Output is correct
10 Correct 3832 ms 168728 KB Output is correct
11 Correct 4014 ms 168848 KB Output is correct
12 Correct 3990 ms 170272 KB Output is correct
13 Correct 3918 ms 168728 KB Output is correct
14 Correct 3826 ms 168692 KB Output is correct
15 Correct 1229 ms 160908 KB Output is correct
16 Correct 1285 ms 160788 KB Output is correct
17 Correct 1311 ms 160992 KB Output is correct
18 Correct 1311 ms 160932 KB Output is correct
19 Correct 1373 ms 161076 KB Output is correct
20 Correct 1318 ms 161020 KB Output is correct
21 Correct 1369 ms 160888 KB Output is correct
22 Correct 1312 ms 160852 KB Output is correct
23 Correct 1246 ms 160848 KB Output is correct
24 Correct 1304 ms 161092 KB Output is correct
25 Correct 1304 ms 162140 KB Output is correct
26 Correct 1311 ms 161000 KB Output is correct
27 Correct 3660 ms 161292 KB Output is correct
28 Correct 3954 ms 173120 KB Output is correct
29 Correct 4120 ms 170964 KB Output is correct
30 Correct 4160 ms 170944 KB Output is correct
31 Correct 3811 ms 174216 KB Output is correct
32 Correct 1200 ms 161064 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1867 ms 161448 KB Output is correct
2 Correct 1786 ms 161272 KB Output is correct
3 Correct 1870 ms 161176 KB Output is correct
4 Correct 1783 ms 161156 KB Output is correct
5 Correct 1794 ms 161196 KB Output is correct
6 Correct 3944 ms 172732 KB Output is correct
7 Correct 3867 ms 172768 KB Output is correct
8 Correct 4024 ms 172700 KB Output is correct
9 Correct 3933 ms 173608 KB Output is correct
10 Correct 3842 ms 168816 KB Output is correct
11 Correct 3842 ms 168792 KB Output is correct
12 Correct 3938 ms 170488 KB Output is correct
13 Correct 4040 ms 168776 KB Output is correct
14 Correct 4075 ms 168752 KB Output is correct
15 Correct 1590 ms 172664 KB Output is correct
16 Correct 4312 ms 174328 KB Output is correct
17 Correct 1250 ms 160888 KB Output is correct
18 Correct 1227 ms 161016 KB Output is correct
19 Correct 1281 ms 160864 KB Output is correct
20 Correct 1315 ms 161144 KB Output is correct
21 Correct 1277 ms 161020 KB Output is correct
22 Correct 1197 ms 160928 KB Output is correct
23 Correct 1287 ms 161052 KB Output is correct
24 Correct 1322 ms 161024 KB Output is correct
25 Correct 1278 ms 161092 KB Output is correct
26 Correct 1277 ms 160956 KB Output is correct
27 Correct 1395 ms 162236 KB Output is correct
28 Correct 1248 ms 161160 KB Output is correct
29 Correct 3904 ms 161288 KB Output is correct
30 Correct 4240 ms 173240 KB Output is correct
31 Correct 3879 ms 173380 KB Output is correct
32 Correct 3694 ms 173600 KB Output is correct
33 Correct 3865 ms 171244 KB Output is correct
34 Correct 4123 ms 171496 KB Output is correct
35 Correct 3936 ms 171068 KB Output is correct
36 Correct 4150 ms 171452 KB Output is correct
37 Correct 4255 ms 174256 KB Output is correct
38 Correct 4110 ms 175196 KB Output is correct
39 Correct 1278 ms 160968 KB Output is correct
40 Correct 4320 ms 172764 KB Output is correct