oj.uz

Submission #104370

# Submission time Handle Problem Language Result Execution time Memory
104370 2019-04-05T17:37:59 Z ihdignite Wombats (IOI13_wombats) C++14
100 / 100
 7369 ms 174308 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];

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 6178 ms 168700 KB Output is correct
2 Correct 5958 ms 168616 KB Output is correct
3 Correct 6002 ms 170280 KB Output is correct
4 Correct 5922 ms 168652 KB Output is correct
5 Correct 6191 ms 168524 KB Output is correct
6 Correct 1543 ms 160888 KB Output is correct
7 Correct 1539 ms 160760 KB Output is correct
8 Correct 1528 ms 160616 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1554 ms 160828 KB Output is correct
2 Correct 1569 ms 160760 KB Output is correct
3 Correct 1582 ms 160888 KB Output is correct
4 Correct 1538 ms 160952 KB Output is correct
5 Correct 1529 ms 160904 KB Output is correct
6 Correct 1505 ms 160888 KB Output is correct
7 Correct 1470 ms 160912 KB Output is correct
8 Correct 1608 ms 160924 KB Output is correct
9 Correct 1567 ms 160792 KB Output is correct
10 Correct 1543 ms 160760 KB Output is correct
11 Correct 1611 ms 161968 KB Output is correct
12 Correct 1542 ms 160888 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2495 ms 160968 KB Output is correct
2 Correct 2672 ms 161016 KB Output is correct
3 Correct 2443 ms 161116 KB Output is correct
4 Correct 2214 ms 161080 KB Output is correct
5 Correct 2379 ms 161064 KB Output is correct
6 Correct 1635 ms 160816 KB Output is correct
7 Correct 1584 ms 160864 KB Output is correct
8 Correct 1599 ms 160816 KB Output is correct
9 Correct 5900 ms 161056 KB Output is correct
10 Correct 1582 ms 160744 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6451 ms 172492 KB Output is correct
2 Correct 6459 ms 172608 KB Output is correct
3 Correct 6366 ms 172660 KB Output is correct
4 Correct 6068 ms 173312 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2398 ms 161224 KB Output is correct
2 Correct 2461 ms 161148 KB Output is correct
3 Correct 2463 ms 161016 KB Output is correct
4 Correct 2467 ms 161128 KB Output is correct
5 Correct 2490 ms 161036 KB Output is correct
6 Correct 6267 ms 172596 KB Output is correct
7 Correct 6277 ms 172536 KB Output is correct
8 Correct 6005 ms 172612 KB Output is correct
9 Correct 6327 ms 173432 KB Output is correct
10 Correct 6670 ms 168724 KB Output is correct
11 Correct 6144 ms 168772 KB Output is correct
12 Correct 6309 ms 170104 KB Output is correct
13 Correct 6158 ms 168616 KB Output is correct
14 Correct 6159 ms 168656 KB Output is correct
15 Correct 1476 ms 160760 KB Output is correct
16 Correct 1544 ms 160860 KB Output is correct
17 Correct 1535 ms 160764 KB Output is correct
18 Correct 1528 ms 160680 KB Output is correct
19 Correct 1445 ms 160968 KB Output is correct
20 Correct 1592 ms 160860 KB Output is correct
21 Correct 1554 ms 160920 KB Output is correct
22 Correct 1462 ms 160936 KB Output is correct
23 Correct 1491 ms 160904 KB Output is correct
24 Correct 1502 ms 160888 KB Output is correct
25 Correct 1653 ms 161700 KB Output is correct
26 Correct 1471 ms 160844 KB Output is correct
27 Correct 5557 ms 161048 KB Output is correct
28 Correct 5587 ms 172980 KB Output is correct
29 Correct 5537 ms 170928 KB Output is correct
30 Correct 5431 ms 170772 KB Output is correct
31 Correct 5507 ms 173940 KB Output is correct
32 Correct 1588 ms 160796 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2366 ms 160900 KB Output is correct
2 Correct 2305 ms 161068 KB Output is correct
3 Correct 2314 ms 161144 KB Output is correct
4 Correct 2522 ms 160956 KB Output is correct
5 Correct 2528 ms 161048 KB Output is correct
6 Correct 6274 ms 172612 KB Output is correct
7 Correct 6052 ms 172632 KB Output is correct
8 Correct 6364 ms 172508 KB Output is correct
9 Correct 6026 ms 173436 KB Output is correct
10 Correct 6061 ms 168660 KB Output is correct
11 Correct 6161 ms 168696 KB Output is correct
12 Correct 6022 ms 170156 KB Output is correct
13 Correct 5981 ms 168708 KB Output is correct
14 Correct 6049 ms 168572 KB Output is correct
15 Correct 1882 ms 172536 KB Output is correct
16 Correct 6933 ms 174308 KB Output is correct
17 Correct 1573 ms 160888 KB Output is correct
18 Correct 1521 ms 160760 KB Output is correct
19 Correct 1488 ms 160848 KB Output is correct
20 Correct 1536 ms 160888 KB Output is correct
21 Correct 1426 ms 160892 KB Output is correct
22 Correct 1482 ms 160760 KB Output is correct
23 Correct 1434 ms 160692 KB Output is correct
24 Correct 1463 ms 160924 KB Output is correct
25 Correct 1428 ms 160688 KB Output is correct
26 Correct 1447 ms 160792 KB Output is correct
27 Correct 1549 ms 161808 KB Output is correct
28 Correct 1535 ms 160888 KB Output is correct
29 Correct 5215 ms 160960 KB Output is correct
30 Correct 5161 ms 173008 KB Output is correct
31 Correct 5887 ms 173416 KB Output is correct
32 Correct 6002 ms 173156 KB Output is correct
33 Correct 5541 ms 170920 KB Output is correct
34 Correct 6472 ms 171436 KB Output is correct
35 Correct 5387 ms 170716 KB Output is correct
36 Correct 6652 ms 171100 KB Output is correct
37 Correct 5177 ms 174028 KB Output is correct
38 Correct 5937 ms 173984 KB Output is correct
39 Correct 1561 ms 160784 KB Output is correct
40 Correct 7369 ms 171160 KB Output is correct