oj.uz

Submission #65037

# Submission time Handle Problem Language Result Execution time Memory
65037 2018-08-06T13:26:31 Z gnoor Wombats (IOI13_wombats) C++17
55 / 100
 6650 ms 263168 KB 
#include "wombats.h"

#include <vector>
#include <cmath>
#include <cstdio>

using namespace std;

typedef vector<vector<int>> tbl;

int r,c;

int opt[200][200];
tbl combine(const tbl &a, const tbl &b) {
	tbl tmp(c,vector<int>(c,1e9));
	for (int sz=-c+1;sz<c;sz++) {
		for (int i=0;i<c;i++) {
			int j=i+sz;
			if (j<0||j>=c) continue;
			for (int k=(j==0?0:opt[i][j-1]);k<=(i==c-1?c-1:opt[i+1][j]);k++) {
				if (a[i][k]+b[k][j]<tmp[i][j]) {
					tmp[i][j]=a[i][k]+b[k][j];
					opt[i][j]=k;
				}
			}
		}
	}
	return tmp;
}

int h[5000][200];
int v[5000][200];

int qsh[5000][200];

//0 <= row < r-1
tbl build(int row) {
	tbl tmp(c,vector<int>(c,1e9));
	int da,db;
	for (int sz=-c+1;sz<c;sz++) {
		for (int i=0;i<c;i++) {
			int j=i+sz;
			if (j<0||j>=c) continue;
			for (int k=(j==0?0:opt[i][j-1]);k<=(i==c-1?c-1:opt[i+1][j]);k++) {
				da=abs((k==0?0:qsh[row][k-1])-(i==0?0:qsh[row][i-1]));
				db=abs((k==0?0:qsh[row+1][k-1])-(j==0?0:qsh[row+1][j-1]));
				if (da+db+v[row][k]<tmp[i][j]) {
					tmp[i][j]=da+db+v[row][k];
					opt[i][j]=k;
				}
			}
		}
	}
	return tmp;
}

tbl seg[30100];

void buildseg(int id,int ll,int rr) {
	if (ll+1==rr) {
		seg[id]=build(ll);
		return;
	}
	int m=(ll+rr)>>1;
	buildseg(id*2,ll,m);
	buildseg(id*2+1,m,rr);
	seg[id]=combine(seg[id*2],seg[id*2+1]);
}

void update(int id,int ll,int rr,int k) {
	if (ll+1==rr) {
		seg[id]=build(ll);
		return;
	}
	int m=(ll+rr)>>1;
	if (k<m) update(id*2,ll,m,k);
	else update(id*2+1,m,rr,k);
	seg[id]=combine(seg[id*2],seg[id*2+1]);
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	r=R;
	c=C;
	for (int i=0;i<R;i++) {
		for (int j=0;j<c;j++) {
			h[i][j]=H[i][j];
			v[i][j]=V[i][j];
		}
	}
	for (int i=0;i<r;i++) {
		qsh[i][0]=h[i][0];
		for (int j=1;j<c-1;j++) {
			qsh[i][j]=qsh[i][j-1]+h[i][j];
		}
	}
	buildseg(1,0,r-1);
}

void changeH(int P, int Q, int W) {
	h[P][Q]=W;
	qsh[P][0]=h[P][0];
	for (int j=1;j<c-1;j++) {
		qsh[P][j]=qsh[P][j-1]+h[P][j];
	}
	update(1,0,r-1,P);
	if (P) update(1,0,r-1,P-1);
}

void changeV(int P, int Q, int W) {
	v[P][Q]=W;
	update(1,0,r-1,P);
}

int escape(int V1, int V2) {
	return seg[1][V1][V2];
}

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;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 17272 KB Output is correct
2 Correct 27 ms 17528 KB Output is correct
3 Correct 118 ms 20268 KB Output is correct
4 Correct 27 ms 20268 KB Output is correct
5 Correct 27 ms 20268 KB Output is correct
6 Correct 4 ms 20268 KB Output is correct
7 Correct 3 ms 20268 KB Output is correct
8 Correct 3 ms 20268 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20268 KB Output is correct
2 Correct 3 ms 20268 KB Output is correct
3 Correct 2 ms 20268 KB Output is correct
4 Correct 5 ms 20268 KB Output is correct
5 Correct 3 ms 20268 KB Output is correct
6 Correct 5 ms 20268 KB Output is correct
7 Correct 5 ms 20268 KB Output is correct
8 Correct 5 ms 20268 KB Output is correct
9 Correct 4 ms 20268 KB Output is correct
10 Correct 5 ms 20268 KB Output is correct
11 Correct 106 ms 20268 KB Output is correct
12 Correct 5 ms 20268 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 20268 KB Output is correct
2 Correct 199 ms 20268 KB Output is correct
3 Correct 522 ms 20268 KB Output is correct
4 Correct 270 ms 20268 KB Output is correct
5 Correct 351 ms 20268 KB Output is correct
6 Correct 3 ms 20268 KB Output is correct
7 Correct 3 ms 20268 KB Output is correct
8 Correct 4 ms 20268 KB Output is correct
9 Correct 1341 ms 20268 KB Output is correct
10 Correct 3 ms 20268 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 25528 KB Output is correct
2 Correct 32 ms 25604 KB Output is correct
3 Correct 32 ms 25716 KB Output is correct
4 Correct 81 ms 27136 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 27136 KB Output is correct
2 Correct 182 ms 27136 KB Output is correct
3 Correct 434 ms 27136 KB Output is correct
4 Correct 258 ms 27136 KB Output is correct
5 Correct 296 ms 27136 KB Output is correct
6 Correct 33 ms 27136 KB Output is correct
7 Correct 26 ms 27136 KB Output is correct
8 Correct 27 ms 27136 KB Output is correct
9 Correct 102 ms 28408 KB Output is correct
10 Correct 24 ms 28408 KB Output is correct
11 Correct 24 ms 28408 KB Output is correct
12 Correct 129 ms 28408 KB Output is correct
13 Correct 24 ms 28408 KB Output is correct
14 Correct 23 ms 28408 KB Output is correct
15 Correct 3 ms 28408 KB Output is correct
16 Correct 4 ms 28408 KB Output is correct
17 Correct 3 ms 28408 KB Output is correct
18 Correct 5 ms 28408 KB Output is correct
19 Correct 4 ms 28408 KB Output is correct
20 Correct 4 ms 28408 KB Output is correct
21 Correct 5 ms 28408 KB Output is correct
22 Correct 5 ms 28408 KB Output is correct
23 Correct 4 ms 28408 KB Output is correct
24 Correct 4 ms 28408 KB Output is correct
25 Correct 113 ms 28408 KB Output is correct
26 Correct 6 ms 28408 KB Output is correct
27 Correct 1401 ms 28408 KB Output is correct
28 Runtime error 6650 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 386 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -