oj.uz

Submission #104364

# Submission time Handle Problem Language Result Execution time Memory
104364 2019-04-05T17:15:07 Z ihdignite Wombats (IOI13_wombats) C++14
43 / 100
 6513 ms 174100 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], 0x3d, 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 5900 ms 168576 KB Output is correct
2 Correct 5496 ms 168568 KB Output is correct
3 Correct 5654 ms 170180 KB Output is correct
4 Correct 5887 ms 168568 KB Output is correct
5 Correct 6034 ms 168656 KB Output is correct
6 Correct 1443 ms 160784 KB Output is correct
7 Correct 1429 ms 160956 KB Output is correct
8 Correct 1399 ms 160760 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1536 ms 160640 KB Output is correct
2 Correct 1594 ms 160888 KB Output is correct
3 Correct 1562 ms 160760 KB Output is correct
4 Correct 1600 ms 160764 KB Output is correct
5 Incorrect 1576 ms 160896 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 2378 ms 161096 KB Output is correct
2 Correct 2485 ms 161104 KB Output is correct
3 Correct 2442 ms 161044 KB Output is correct
4 Correct 2496 ms 161120 KB Output is correct
5 Correct 2460 ms 160984 KB Output is correct
6 Correct 1410 ms 160860 KB Output is correct
7 Correct 1551 ms 160704 KB Output is correct
8 Correct 1532 ms 160764 KB Output is correct
9 Correct 6082 ms 161160 KB Output is correct
10 Correct 1482 ms 160892 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6058 ms 172556 KB Output is correct
2 Correct 5993 ms 172792 KB Output is correct
3 Correct 5552 ms 172496 KB Output is correct
4 Correct 6049 ms 173452 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2456 ms 160992 KB Output is correct
2 Correct 2396 ms 161144 KB Output is correct
3 Correct 2277 ms 161100 KB Output is correct
4 Correct 2291 ms 160992 KB Output is correct
5 Correct 2451 ms 161128 KB Output is correct
6 Correct 5991 ms 172612 KB Output is correct
7 Correct 5926 ms 172620 KB Output is correct
8 Correct 5476 ms 172644 KB Output is correct
9 Correct 5591 ms 173376 KB Output is correct
10 Correct 5685 ms 168568 KB Output is correct
11 Correct 5661 ms 168708 KB Output is correct
12 Correct 5906 ms 170208 KB Output is correct
13 Correct 5491 ms 168660 KB Output is correct
14 Correct 5753 ms 168560 KB Output is correct
15 Correct 1519 ms 160692 KB Output is correct
16 Correct 1550 ms 160700 KB Output is correct
17 Correct 1415 ms 160992 KB Output is correct
18 Correct 1406 ms 160860 KB Output is correct
19 Incorrect 1494 ms 160960 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2454 ms 160880 KB Output is correct
2 Correct 2360 ms 161016 KB Output is correct
3 Correct 2330 ms 161020 KB Output is correct
4 Correct 2477 ms 161024 KB Output is correct
5 Correct 2271 ms 160972 KB Output is correct
6 Correct 5687 ms 172664 KB Output is correct
7 Correct 5379 ms 172652 KB Output is correct
8 Correct 5451 ms 172536 KB Output is correct
9 Correct 6150 ms 173344 KB Output is correct
10 Correct 6154 ms 168572 KB Output is correct
11 Correct 5444 ms 168572 KB Output is correct
12 Correct 6267 ms 170160 KB Output is correct
13 Correct 5449 ms 168744 KB Output is correct
14 Correct 5768 ms 168568 KB Output is correct
15 Correct 1782 ms 172408 KB Output is correct
16 Correct 6513 ms 174100 KB Output is correct
17 Correct 1464 ms 160632 KB Output is correct
18 Correct 1580 ms 160888 KB Output is correct
19 Correct 1396 ms 160760 KB Output is correct
20 Correct 1553 ms 160932 KB Output is correct
21 Incorrect 1545 ms 160864 KB Output isn't correct
22 Halted 0 ms 0 KB -