oj.uz

Submission #104360

# Submission time Handle Problem Language Result Execution time Memory
104360 2019-04-05T16:41:28 Z ihdignite Wombats (IOI13_wombats) C++14
43 / 100
 7075 ms 183428 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;
	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);
}

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, 0x3e, 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:105:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
 }
 ^
wombats.cpp:105:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp:105:1: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
wombats.cpp: In function 'void solve(int*, int (*)[200], int*, int, int, int, int)':
wombats.cpp:21:7: warning: 'm2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  solve(a, b, d, l1, m1-1, l2, m2);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void cs(int, int, int)':
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 5958 ms 168684 KB Output is correct
2 Correct 5528 ms 168696 KB Output is correct
3 Correct 6621 ms 171380 KB Output is correct
4 Correct 5859 ms 168764 KB Output is correct
5 Correct 5813 ms 168832 KB Output is correct
6 Correct 1433 ms 160888 KB Output is correct
7 Correct 1664 ms 160788 KB Output is correct
8 Correct 1631 ms 160752 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1475 ms 160856 KB Output is correct
2 Correct 1488 ms 160832 KB Output is correct
3 Correct 1425 ms 160760 KB Output is correct
4 Correct 1452 ms 160760 KB Output is correct
5 Incorrect 1667 ms 160888 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 2431 ms 161152 KB Output is correct
2 Correct 2262 ms 161092 KB Output is correct
3 Correct 2347 ms 161328 KB Output is correct
4 Correct 2252 ms 161144 KB Output is correct
5 Correct 2531 ms 161168 KB Output is correct
6 Correct 1448 ms 160760 KB Output is correct
7 Correct 1452 ms 160760 KB Output is correct
8 Correct 1551 ms 160888 KB Output is correct
9 Correct 5977 ms 161216 KB Output is correct
10 Correct 1458 ms 161028 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5760 ms 172796 KB Output is correct
2 Correct 5760 ms 172792 KB Output is correct
3 Correct 5911 ms 172536 KB Output is correct
4 Correct 6084 ms 174072 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2479 ms 161064 KB Output is correct
2 Correct 2286 ms 161052 KB Output is correct
3 Correct 2388 ms 161016 KB Output is correct
4 Correct 2540 ms 161140 KB Output is correct
5 Correct 2516 ms 161148 KB Output is correct
6 Correct 6265 ms 172584 KB Output is correct
7 Correct 6341 ms 172596 KB Output is correct
8 Correct 6015 ms 172684 KB Output is correct
9 Correct 6176 ms 174092 KB Output is correct
10 Correct 6061 ms 168660 KB Output is correct
11 Correct 6012 ms 168604 KB Output is correct
12 Correct 6190 ms 171388 KB Output is correct
13 Correct 6318 ms 168672 KB Output is correct
14 Correct 6144 ms 168588 KB Output is correct
15 Correct 1543 ms 160872 KB Output is correct
16 Correct 1482 ms 161016 KB Output is correct
17 Correct 1504 ms 160784 KB Output is correct
18 Correct 1577 ms 160980 KB Output is correct
19 Incorrect 1621 ms 160888 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2552 ms 161308 KB Output is correct
2 Correct 2628 ms 161112 KB Output is correct
3 Correct 2515 ms 161148 KB Output is correct
4 Correct 2349 ms 161056 KB Output is correct
5 Correct 2418 ms 161144 KB Output is correct
6 Correct 5597 ms 172692 KB Output is correct
7 Correct 5423 ms 172648 KB Output is correct
8 Correct 5677 ms 172664 KB Output is correct
9 Correct 6190 ms 174260 KB Output is correct
10 Correct 5887 ms 168608 KB Output is correct
11 Correct 6096 ms 168628 KB Output is correct
12 Correct 6262 ms 171292 KB Output is correct
13 Correct 6171 ms 168696 KB Output is correct
14 Correct 5729 ms 168568 KB Output is correct
15 Correct 1812 ms 182264 KB Output is correct
16 Correct 7075 ms 183428 KB Output is correct
17 Correct 1545 ms 160832 KB Output is correct
18 Correct 1444 ms 160760 KB Output is correct
19 Correct 1509 ms 160888 KB Output is correct
20 Correct 1511 ms 160888 KB Output is correct
21 Incorrect 1567 ms 160844 KB Output isn't correct
22 Halted 0 ms 0 KB -