oj.uz

Submission #118871

# Submission time Handle Problem Language Result Execution time Memory
118871 2019-06-20T00:16:28 Z tmwilliamlin168 Wombats (IOI13_wombats) C++14
100 / 100
 3904 ms 183532 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 3315 ms 168688 KB Output is correct
2 Correct 3245 ms 168548 KB Output is correct
3 Correct 3332 ms 171260 KB Output is correct
4 Correct 3355 ms 168588 KB Output is correct
5 Correct 3357 ms 168580 KB Output is correct
6 Correct 1162 ms 160716 KB Output is correct
7 Correct 1165 ms 160708 KB Output is correct
8 Correct 1163 ms 160652 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1168 ms 160776 KB Output is correct
2 Correct 1153 ms 160716 KB Output is correct
3 Correct 1156 ms 160760 KB Output is correct
4 Correct 1180 ms 160700 KB Output is correct
5 Correct 1186 ms 160768 KB Output is correct
6 Correct 1201 ms 160968 KB Output is correct
7 Correct 1463 ms 160744 KB Output is correct
8 Correct 1167 ms 160860 KB Output is correct
9 Correct 1170 ms 160892 KB Output is correct
10 Correct 1157 ms 160888 KB Output is correct
11 Correct 1246 ms 163192 KB Output is correct
12 Correct 1167 ms 160984 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1629 ms 161300 KB Output is correct
2 Correct 1627 ms 160968 KB Output is correct
3 Correct 1646 ms 161148 KB Output is correct
4 Correct 1622 ms 161144 KB Output is correct
5 Correct 1606 ms 161272 KB Output is correct
6 Correct 1170 ms 160760 KB Output is correct
7 Correct 1176 ms 160760 KB Output is correct
8 Correct 1183 ms 160888 KB Output is correct
9 Correct 3412 ms 161068 KB Output is correct
10 Correct 1188 ms 160920 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3539 ms 172604 KB Output is correct
2 Correct 3386 ms 172524 KB Output is correct
3 Correct 3463 ms 172536 KB Output is correct
4 Correct 3428 ms 173884 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1645 ms 161056 KB Output is correct
2 Correct 1586 ms 161040 KB Output is correct
3 Correct 1592 ms 161084 KB Output is correct
4 Correct 1595 ms 161136 KB Output is correct
5 Correct 1630 ms 161144 KB Output is correct
6 Correct 3298 ms 172536 KB Output is correct
7 Correct 3323 ms 172644 KB Output is correct
8 Correct 3339 ms 172836 KB Output is correct
9 Correct 3359 ms 174072 KB Output is correct
10 Correct 3524 ms 168680 KB Output is correct
11 Correct 3264 ms 168764 KB Output is correct
12 Correct 3357 ms 171488 KB Output is correct
13 Correct 3341 ms 168696 KB Output is correct
14 Correct 3356 ms 168696 KB Output is correct
15 Correct 1194 ms 160888 KB Output is correct
16 Correct 1195 ms 160740 KB Output is correct
17 Correct 1173 ms 160888 KB Output is correct
18 Correct 1175 ms 160828 KB Output is correct
19 Correct 1186 ms 160880 KB Output is correct
20 Correct 1176 ms 160912 KB Output is correct
21 Correct 1176 ms 160888 KB Output is correct
22 Correct 1184 ms 161016 KB Output is correct
23 Correct 1268 ms 160888 KB Output is correct
24 Correct 1191 ms 160884 KB Output is correct
25 Correct 1245 ms 163192 KB Output is correct
26 Correct 1238 ms 160804 KB Output is correct
27 Correct 3256 ms 161344 KB Output is correct
28 Correct 3413 ms 176688 KB Output is correct
29 Correct 3460 ms 174328 KB Output is correct
30 Correct 3492 ms 174460 KB Output is correct
31 Correct 3627 ms 178428 KB Output is correct
32 Correct 1193 ms 160844 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1736 ms 161096 KB Output is correct
2 Correct 1737 ms 161272 KB Output is correct
3 Correct 1630 ms 161328 KB Output is correct
4 Correct 1580 ms 161144 KB Output is correct
5 Correct 1589 ms 161144 KB Output is correct
6 Correct 3281 ms 172732 KB Output is correct
7 Correct 3300 ms 172676 KB Output is correct
8 Correct 3346 ms 172496 KB Output is correct
9 Correct 3339 ms 174140 KB Output is correct
10 Correct 3325 ms 168568 KB Output is correct
11 Correct 3290 ms 168568 KB Output is correct
12 Correct 3382 ms 171356 KB Output is correct
13 Correct 3488 ms 168696 KB Output is correct
14 Correct 3361 ms 168816 KB Output is correct
15 Correct 1372 ms 182332 KB Output is correct
16 Correct 3760 ms 183532 KB Output is correct
17 Correct 1203 ms 160972 KB Output is correct
18 Correct 1169 ms 160856 KB Output is correct
19 Correct 1144 ms 160860 KB Output is correct
20 Correct 1176 ms 160696 KB Output is correct
21 Correct 1177 ms 160700 KB Output is correct
22 Correct 1155 ms 160784 KB Output is correct
23 Correct 1155 ms 160780 KB Output is correct
24 Correct 1166 ms 160788 KB Output is correct
25 Correct 1160 ms 160764 KB Output is correct
26 Correct 1158 ms 160992 KB Output is correct
27 Correct 1250 ms 163384 KB Output is correct
28 Correct 1181 ms 160916 KB Output is correct
29 Correct 3422 ms 161144 KB Output is correct
30 Correct 3410 ms 176760 KB Output is correct
31 Correct 3273 ms 180928 KB Output is correct
32 Correct 3313 ms 180976 KB Output is correct
33 Correct 3442 ms 174260 KB Output is correct
34 Correct 3641 ms 178288 KB Output is correct
35 Correct 3567 ms 174264 KB Output is correct
36 Correct 3687 ms 178192 KB Output is correct
37 Correct 3618 ms 178352 KB Output is correct
38 Correct 3458 ms 181448 KB Output is correct
39 Correct 1199 ms 160888 KB Output is correct
40 Correct 3904 ms 178536 KB Output is correct