oj.uz

Submission #104367

# Submission time Handle Problem Language Result Execution time Memory
104367 2019-04-05T17:26:52 Z ihdignite Wombats (IOI13_wombats) C++14
100 / 100
 7261 ms 181576 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) {
	//cout << "s " << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
	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;
		}
	}
	//if(l1==0&&r1==c-1)
	//cout << "sr " << m1 << " " << m2 << endl;
	solve(a, b, d, l1, m1-1, l2, m2);
	solve(a, b, d, m1+1, r1, m2, r2);
}

void p(int i) {
	//cout << "p " << i << endl;
	//for(int j=0; j<5; ++j)
		//for(int k=0; k<5; ++k)
			//cout << st[i][j][k] << " \n"[k==5-1];
}

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];
		}
	}
	p(i);
}

void cmb(int i) {
	//cout << "cmb " << i << " " << 2*i << " " << 2*i+1 << endl;
	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]);
	p(i);
}

//just do upd(0, bc-1)
void bld(int i=1, int l2=0, int r2=bc-1) {
	if(l2==r2) {
		cs(i, l2, r2);
		return;
	}
	int m2=(l2+r2)/2;
	bld(2*i, l2, m2);
	bld(2*i+1, m2+1, r2);
	cmb(i);
}

void upd(int l1, int i=1, int l2=0, int r2=bc-1) {
	//cout << "u " << l1 << " " << i << " " << l2 << " " << r2 << endl;
	//cout << h[0][1];
	if(l2==r2) {
		cs(i, l2, r2);
		return;
	}
	int m2=(l2+r2)/2;
	if(l1<=m2)
		upd(l1, 2*i, l2, m2);
	else
		upd(l1, 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];
	bld();
}

void changeH(int p, int q, int w) {
	h[p][q]=w;
	upd(p/bs);
}

void changeV(int p, int q, int w) {
	v[p][q]=w;
	upd(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:106:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:106:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:106:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:32: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:32:6: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:32: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 6349 ms 168604 KB Output is correct
2 Correct 6086 ms 168568 KB Output is correct
3 Correct 6221 ms 170372 KB Output is correct
4 Correct 6031 ms 168816 KB Output is correct
5 Correct 6294 ms 168760 KB Output is correct
6 Correct 1476 ms 160760 KB Output is correct
7 Correct 1470 ms 160720 KB Output is correct
8 Correct 1472 ms 160760 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1499 ms 160792 KB Output is correct
2 Correct 1441 ms 160760 KB Output is correct
3 Correct 1450 ms 160780 KB Output is correct
4 Correct 1593 ms 160832 KB Output is correct
5 Correct 1505 ms 160888 KB Output is correct
6 Correct 1413 ms 160936 KB Output is correct
7 Correct 1415 ms 160892 KB Output is correct
8 Correct 1533 ms 160864 KB Output is correct
9 Correct 1442 ms 160736 KB Output is correct
10 Correct 1432 ms 161036 KB Output is correct
11 Correct 1455 ms 161912 KB Output is correct
12 Correct 1405 ms 160820 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2174 ms 161132 KB Output is correct
2 Correct 2253 ms 160888 KB Output is correct
3 Correct 2259 ms 161104 KB Output is correct
4 Correct 2221 ms 161016 KB Output is correct
5 Correct 2614 ms 161016 KB Output is correct
6 Correct 1468 ms 160800 KB Output is correct
7 Correct 1467 ms 160696 KB Output is correct
8 Correct 1457 ms 160760 KB Output is correct
9 Correct 5246 ms 161064 KB Output is correct
10 Correct 1468 ms 160760 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5970 ms 172476 KB Output is correct
2 Correct 5874 ms 172564 KB Output is correct
3 Correct 6059 ms 172492 KB Output is correct
4 Correct 6252 ms 173392 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2230 ms 161004 KB Output is correct
2 Correct 2397 ms 161144 KB Output is correct
3 Correct 2357 ms 161016 KB Output is correct
4 Correct 2493 ms 161144 KB Output is correct
5 Correct 2386 ms 161024 KB Output is correct
6 Correct 6278 ms 172500 KB Output is correct
7 Correct 6278 ms 172540 KB Output is correct
8 Correct 5947 ms 172612 KB Output is correct
9 Correct 5967 ms 173416 KB Output is correct
10 Correct 6338 ms 168592 KB Output is correct
11 Correct 5903 ms 168704 KB Output is correct
12 Correct 6159 ms 170160 KB Output is correct
13 Correct 6184 ms 168568 KB Output is correct
14 Correct 6175 ms 168724 KB Output is correct
15 Correct 1583 ms 160736 KB Output is correct
16 Correct 1526 ms 160844 KB Output is correct
17 Correct 1462 ms 160944 KB Output is correct
18 Correct 1453 ms 160820 KB Output is correct
19 Correct 1514 ms 160952 KB Output is correct
20 Correct 1549 ms 160888 KB Output is correct
21 Correct 1556 ms 160892 KB Output is correct
22 Correct 1488 ms 160924 KB Output is correct
23 Correct 1666 ms 160832 KB Output is correct
24 Correct 1653 ms 160884 KB Output is correct
25 Correct 1652 ms 163188 KB Output is correct
26 Correct 1558 ms 160708 KB Output is correct
27 Correct 5733 ms 161100 KB Output is correct
28 Correct 5313 ms 176916 KB Output is correct
29 Correct 5999 ms 174240 KB Output is correct
30 Correct 6252 ms 174476 KB Output is correct
31 Correct 5440 ms 178424 KB Output is correct
32 Correct 1453 ms 160848 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2227 ms 161120 KB Output is correct
2 Correct 2335 ms 161016 KB Output is correct
3 Correct 2295 ms 160964 KB Output is correct
4 Correct 2350 ms 161016 KB Output is correct
5 Correct 2358 ms 161112 KB Output is correct
6 Correct 6264 ms 172528 KB Output is correct
7 Correct 6298 ms 172592 KB Output is correct
8 Correct 6306 ms 172588 KB Output is correct
9 Correct 6552 ms 173372 KB Output is correct
10 Correct 6353 ms 168696 KB Output is correct
11 Correct 6334 ms 168696 KB Output is correct
12 Correct 6411 ms 170108 KB Output is correct
13 Correct 6005 ms 168632 KB Output is correct
14 Correct 6316 ms 168612 KB Output is correct
15 Correct 1676 ms 172568 KB Output is correct
16 Correct 6584 ms 174224 KB Output is correct
17 Correct 1434 ms 160788 KB Output is correct
18 Correct 1406 ms 160832 KB Output is correct
19 Correct 1463 ms 160932 KB Output is correct
20 Correct 1469 ms 160928 KB Output is correct
21 Correct 1527 ms 161016 KB Output is correct
22 Correct 1571 ms 160848 KB Output is correct
23 Correct 1475 ms 160916 KB Output is correct
24 Correct 1548 ms 160944 KB Output is correct
25 Correct 1572 ms 160904 KB Output is correct
26 Correct 1565 ms 160888 KB Output is correct
27 Correct 1504 ms 163192 KB Output is correct
28 Correct 1408 ms 160912 KB Output is correct
29 Correct 5164 ms 161256 KB Output is correct
30 Correct 5346 ms 176760 KB Output is correct
31 Correct 5821 ms 181056 KB Output is correct
32 Correct 6315 ms 180936 KB Output is correct
33 Correct 5682 ms 174360 KB Output is correct
34 Correct 6477 ms 178500 KB Output is correct
35 Correct 5464 ms 174428 KB Output is correct
36 Correct 7261 ms 178372 KB Output is correct
37 Correct 5731 ms 178552 KB Output is correct
38 Correct 5970 ms 181576 KB Output is correct
39 Correct 1512 ms 160784 KB Output is correct
40 Correct 7205 ms 178492 KB Output is correct