oj.uz

Submission #104363

# Submission time Handle Problem Language Result Execution time Memory
104363 2019-04-05T17:10:26 Z ihdignite Wombats (IOI13_wombats) C++14
43 / 100
 6938 ms 174108 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<4; ++j)
		//for(int k=0; k<4; ++k)
			//cout << st[i][j][k] << " \n"[k==4-1];
}

void cs(int i, int l2, int r2) {
	memset(st[i], 0x3e, 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 5747 ms 168596 KB Output is correct
2 Correct 5286 ms 168572 KB Output is correct
3 Correct 5532 ms 170264 KB Output is correct
4 Correct 5701 ms 168600 KB Output is correct
5 Correct 6014 ms 168572 KB Output is correct
6 Correct 1528 ms 160888 KB Output is correct
7 Correct 1519 ms 160860 KB Output is correct
8 Correct 1654 ms 160852 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1608 ms 160788 KB Output is correct
2 Correct 1564 ms 160860 KB Output is correct
3 Correct 1566 ms 160888 KB Output is correct
4 Correct 1656 ms 160784 KB Output is correct
5 Incorrect 1538 ms 160864 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2435 ms 161056 KB Output is correct
2 Correct 2249 ms 160976 KB Output is correct
3 Correct 2603 ms 161144 KB Output is correct
4 Correct 2469 ms 161016 KB Output is correct
5 Correct 2455 ms 160968 KB Output is correct
6 Correct 1505 ms 160668 KB Output is correct
7 Correct 1450 ms 160796 KB Output is correct
8 Correct 1562 ms 160908 KB Output is correct
9 Correct 6387 ms 160972 KB Output is correct
10 Correct 1615 ms 160892 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5708 ms 172616 KB Output is correct
2 Correct 5920 ms 172520 KB Output is correct
3 Correct 5382 ms 172584 KB Output is correct
4 Correct 6009 ms 173456 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2380 ms 161092 KB Output is correct
2 Correct 2218 ms 160964 KB Output is correct
3 Correct 2290 ms 161140 KB Output is correct
4 Correct 2464 ms 161100 KB Output is correct
5 Correct 2255 ms 161056 KB Output is correct
6 Correct 5433 ms 172588 KB Output is correct
7 Correct 5995 ms 172476 KB Output is correct
8 Correct 6191 ms 172536 KB Output is correct
9 Correct 5692 ms 173352 KB Output is correct
10 Correct 5627 ms 168692 KB Output is correct
11 Correct 5594 ms 168608 KB Output is correct
12 Correct 5944 ms 170140 KB Output is correct
13 Correct 5484 ms 168592 KB Output is correct
14 Correct 5588 ms 168600 KB Output is correct
15 Correct 1492 ms 160772 KB Output is correct
16 Correct 1417 ms 160716 KB Output is correct
17 Correct 1531 ms 160804 KB Output is correct
18 Correct 1526 ms 160888 KB Output is correct
19 Incorrect 1478 ms 160712 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2452 ms 161284 KB Output is correct
2 Correct 2347 ms 161016 KB Output is correct
3 Correct 2505 ms 161144 KB Output is correct
4 Correct 2534 ms 161048 KB Output is correct
5 Correct 2390 ms 161052 KB Output is correct
6 Correct 5696 ms 172584 KB Output is correct
7 Correct 5391 ms 172664 KB Output is correct
8 Correct 5332 ms 172536 KB Output is correct
9 Correct 5898 ms 173360 KB Output is correct
10 Correct 5657 ms 168720 KB Output is correct
11 Correct 5496 ms 168580 KB Output is correct
12 Correct 5535 ms 170080 KB Output is correct
13 Correct 5836 ms 168700 KB Output is correct
14 Correct 5529 ms 168676 KB Output is correct
15 Correct 1842 ms 172508 KB Output is correct
16 Correct 6938 ms 174108 KB Output is correct
17 Correct 1535 ms 160888 KB Output is correct
18 Correct 1514 ms 160872 KB Output is correct
19 Correct 1405 ms 160812 KB Output is correct
20 Correct 1436 ms 160960 KB Output is correct
21 Incorrect 1556 ms 160852 KB Output isn't correct
22 Halted 0 ms 0 KB -