oj.uz

Submission #108194

# Submission time Handle Problem Language Result Execution time Memory
108194 2019-04-28T03:12:26 Z ihdignite Wombats (IOI13_wombats) C++14
100 / 100
 4263 ms 174140 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+1];

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(o, 0, 4*c);
	for(int j1=0; j1<c; ++j1) {
		for(int j2=c-1; ~j2; --j2) {
			array<int, 2> d{INT_MAX, 0};
			for(int k=o[j2]; k<=o[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[j2]=-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];
	o[::c]=::c-1;
	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:65:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:65:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:65: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 4014 ms 168580 KB Output is correct
2 Correct 3811 ms 168644 KB Output is correct
3 Correct 3739 ms 170184 KB Output is correct
4 Correct 3844 ms 168816 KB Output is correct
5 Correct 3704 ms 168752 KB Output is correct
6 Correct 1335 ms 160840 KB Output is correct
7 Correct 1249 ms 160648 KB Output is correct
8 Correct 1269 ms 160860 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1323 ms 160768 KB Output is correct
2 Correct 1243 ms 160760 KB Output is correct
3 Correct 1329 ms 160716 KB Output is correct
4 Correct 1181 ms 160752 KB Output is correct
5 Correct 1314 ms 160924 KB Output is correct
6 Correct 1353 ms 160888 KB Output is correct
7 Correct 1316 ms 160928 KB Output is correct
8 Correct 1336 ms 160752 KB Output is correct
9 Correct 1221 ms 160960 KB Output is correct
10 Correct 1425 ms 160876 KB Output is correct
11 Correct 1411 ms 162020 KB Output is correct
12 Correct 1337 ms 160840 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1844 ms 161016 KB Output is correct
2 Correct 1634 ms 161016 KB Output is correct
3 Correct 1797 ms 161144 KB Output is correct
4 Correct 1848 ms 161016 KB Output is correct
5 Correct 1903 ms 161196 KB Output is correct
6 Correct 1380 ms 160960 KB Output is correct
7 Correct 1238 ms 160888 KB Output is correct
8 Correct 1270 ms 161020 KB Output is correct
9 Correct 3977 ms 161120 KB Output is correct
10 Correct 1287 ms 160824 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3826 ms 172600 KB Output is correct
2 Correct 3971 ms 172564 KB Output is correct
3 Correct 3677 ms 172536 KB Output is correct
4 Correct 4046 ms 173432 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1864 ms 161008 KB Output is correct
2 Correct 1760 ms 161016 KB Output is correct
3 Correct 1789 ms 161092 KB Output is correct
4 Correct 1785 ms 161144 KB Output is correct
5 Correct 1860 ms 161052 KB Output is correct
6 Correct 3847 ms 172536 KB Output is correct
7 Correct 3876 ms 172480 KB Output is correct
8 Correct 3851 ms 172448 KB Output is correct
9 Correct 3892 ms 173404 KB Output is correct
10 Correct 3798 ms 168756 KB Output is correct
11 Correct 3445 ms 168696 KB Output is correct
12 Correct 3790 ms 170192 KB Output is correct
13 Correct 3758 ms 168564 KB Output is correct
14 Correct 3970 ms 168596 KB Output is correct
15 Correct 1300 ms 160836 KB Output is correct
16 Correct 1299 ms 160760 KB Output is correct
17 Correct 1359 ms 160736 KB Output is correct
18 Correct 1291 ms 160764 KB Output is correct
19 Correct 1347 ms 160992 KB Output is correct
20 Correct 1238 ms 160860 KB Output is correct
21 Correct 1277 ms 160888 KB Output is correct
22 Correct 1171 ms 160888 KB Output is correct
23 Correct 1192 ms 161016 KB Output is correct
24 Correct 1336 ms 160888 KB Output is correct
25 Correct 1382 ms 161780 KB Output is correct
26 Correct 1298 ms 160912 KB Output is correct
27 Correct 4064 ms 161096 KB Output is correct
28 Correct 3831 ms 173012 KB Output is correct
29 Correct 4200 ms 170896 KB Output is correct
30 Correct 4194 ms 170908 KB Output is correct
31 Correct 4104 ms 173988 KB Output is correct
32 Correct 1219 ms 160652 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1798 ms 160960 KB Output is correct
2 Correct 1916 ms 161140 KB Output is correct
3 Correct 1672 ms 160888 KB Output is correct
4 Correct 1878 ms 161144 KB Output is correct
5 Correct 1840 ms 161164 KB Output is correct
6 Correct 3796 ms 172664 KB Output is correct
7 Correct 3756 ms 172536 KB Output is correct
8 Correct 3689 ms 172612 KB Output is correct
9 Correct 3672 ms 173532 KB Output is correct
10 Correct 3641 ms 168568 KB Output is correct
11 Correct 3839 ms 168704 KB Output is correct
12 Correct 3659 ms 170188 KB Output is correct
13 Correct 3929 ms 168580 KB Output is correct
14 Correct 3633 ms 168632 KB Output is correct
15 Correct 1613 ms 172552 KB Output is correct
16 Correct 4238 ms 174140 KB Output is correct
17 Correct 1276 ms 160864 KB Output is correct
18 Correct 1333 ms 160888 KB Output is correct
19 Correct 1308 ms 160784 KB Output is correct
20 Correct 1355 ms 160888 KB Output is correct
21 Correct 1294 ms 161020 KB Output is correct
22 Correct 1333 ms 160888 KB Output is correct
23 Correct 1223 ms 160852 KB Output is correct
24 Correct 1405 ms 160920 KB Output is correct
25 Correct 1352 ms 160928 KB Output is correct
26 Correct 1453 ms 160904 KB Output is correct
27 Correct 1386 ms 161792 KB Output is correct
28 Correct 1262 ms 160820 KB Output is correct
29 Correct 3901 ms 161068 KB Output is correct
30 Correct 3740 ms 172864 KB Output is correct
31 Correct 3618 ms 173200 KB Output is correct
32 Correct 3655 ms 173228 KB Output is correct
33 Correct 4057 ms 170956 KB Output is correct
34 Correct 4119 ms 171240 KB Output is correct
35 Correct 3767 ms 170936 KB Output is correct
36 Correct 4042 ms 171228 KB Output is correct
37 Correct 4118 ms 174072 KB Output is correct
38 Correct 3829 ms 173924 KB Output is correct
39 Correct 1299 ms 160888 KB Output is correct
40 Correct 4263 ms 171032 KB Output is correct