oj.uz

Submission #65112

# Submission time Handle Problem Language Result Execution time Memory
65112 2018-08-06T16:17:39 Z gnoor Wombats (IOI13_wombats) C++17
76 / 100
 12595 ms 263168 KB 
#include "wombats.h"

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

using namespace std;

//typedef vector<vector<int>> tbl;

struct tbl {
	int d[205][205];

	tbl() {
		memset(d,63,sizeof(d));
	}

	int* operator[](int x) {
		return d[x];
	}

	const int* operator[](int x) const {
		return d[x];
	}
};

int r,c;

int opt[200][200];
tbl combine(const tbl &a, const tbl &b) {
	tbl tmp;
	for (int sz=-c+1;sz<c;sz++) {
		for (int i=max(-sz,0);i<min(c-sz,c);i++) {
			int j=i+sz;
			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];

tbl build(int row) {
	tbl tmp;
	for (int i=0;i<c;i++) {
		for (int j=0;j<c;j++) {
			tmp[i][j]=abs((i==0?0:qsh[row][i-1])-(j==0?0:qsh[row][j-1]))+v[row][j];
		}
	}
	return tmp;
}

tbl seg[1100];

void buildseg(int id,int ll,int rr) {
	if (ll+20>=rr) {
		seg[id]=build(ll);
		for (int i=ll+1;i<rr;i++) {
			seg[id]=combine(seg[id],build(i));
		}
		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+20>=rr) {
		seg[id]=build(ll);
		for (int i=ll+1;i<rr;i++) {
			seg[id]=combine(seg[id],build(i));
		}
		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);
}

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];
	}
	if (P) update(1,0,r,P);
	else update(1,0,r,P);
}

void changeV(int P, int Q, int W) {
	v[P][Q]=W;
	update(1,0,r,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 888 ms 199416 KB Output is correct
2 Correct 834 ms 199652 KB Output is correct
3 Correct 925 ms 202268 KB Output is correct
4 Correct 897 ms 202268 KB Output is correct
5 Correct 850 ms 202268 KB Output is correct
6 Correct 150 ms 202268 KB Output is correct
7 Correct 148 ms 202268 KB Output is correct
8 Correct 157 ms 202268 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 202268 KB Output is correct
2 Correct 176 ms 202268 KB Output is correct
3 Correct 154 ms 202268 KB Output is correct
4 Correct 154 ms 202268 KB Output is correct
5 Correct 159 ms 202268 KB Output is correct
6 Correct 167 ms 202268 KB Output is correct
7 Correct 145 ms 202268 KB Output is correct
8 Correct 156 ms 202268 KB Output is correct
9 Correct 163 ms 202268 KB Output is correct
10 Correct 147 ms 202268 KB Output is correct
11 Correct 228 ms 202268 KB Output is correct
12 Correct 153 ms 202268 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 202268 KB Output is correct
2 Correct 372 ms 202268 KB Output is correct
3 Correct 469 ms 202268 KB Output is correct
4 Correct 537 ms 202268 KB Output is correct
5 Correct 413 ms 202268 KB Output is correct
6 Correct 163 ms 202268 KB Output is correct
7 Correct 152 ms 202268 KB Output is correct
8 Correct 147 ms 202268 KB Output is correct
9 Correct 1343 ms 202268 KB Output is correct
10 Correct 150 ms 202268 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 851 ms 206492 KB Output is correct
2 Correct 804 ms 206556 KB Output is correct
3 Correct 791 ms 206556 KB Output is correct
4 Correct 930 ms 208036 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 208036 KB Output is correct
2 Correct 391 ms 208036 KB Output is correct
3 Correct 487 ms 208036 KB Output is correct
4 Correct 483 ms 208036 KB Output is correct
5 Correct 439 ms 208036 KB Output is correct
6 Correct 889 ms 208036 KB Output is correct
7 Correct 878 ms 208036 KB Output is correct
8 Correct 893 ms 208036 KB Output is correct
9 Correct 984 ms 208872 KB Output is correct
10 Correct 884 ms 208872 KB Output is correct
11 Correct 898 ms 208872 KB Output is correct
12 Correct 991 ms 208872 KB Output is correct
13 Correct 933 ms 208872 KB Output is correct
14 Correct 867 ms 208872 KB Output is correct
15 Correct 144 ms 208872 KB Output is correct
16 Correct 157 ms 208872 KB Output is correct
17 Correct 155 ms 208872 KB Output is correct
18 Correct 174 ms 208872 KB Output is correct
19 Correct 147 ms 208872 KB Output is correct
20 Correct 150 ms 208872 KB Output is correct
21 Correct 149 ms 208872 KB Output is correct
22 Correct 155 ms 208872 KB Output is correct
23 Correct 148 ms 208872 KB Output is correct
24 Correct 160 ms 208872 KB Output is correct
25 Correct 240 ms 208872 KB Output is correct
26 Correct 152 ms 208872 KB Output is correct
27 Correct 1461 ms 208872 KB Output is correct
28 Correct 3712 ms 215152 KB Output is correct
29 Correct 3402 ms 215340 KB Output is correct
30 Correct 3664 ms 218796 KB Output is correct
31 Correct 3672 ms 227744 KB Output is correct
32 Correct 150 ms 227744 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 227744 KB Output is correct
2 Correct 383 ms 227744 KB Output is correct
3 Correct 479 ms 227744 KB Output is correct
4 Correct 474 ms 227744 KB Output is correct
5 Correct 413 ms 227744 KB Output is correct
6 Correct 909 ms 227744 KB Output is correct
7 Correct 856 ms 227744 KB Output is correct
8 Correct 859 ms 227744 KB Output is correct
9 Correct 922 ms 227744 KB Output is correct
10 Correct 856 ms 227744 KB Output is correct
11 Correct 832 ms 227744 KB Output is correct
12 Correct 896 ms 227744 KB Output is correct
13 Correct 818 ms 227744 KB Output is correct
14 Correct 862 ms 227744 KB Output is correct
15 Correct 3448 ms 238220 KB Output is correct
16 Correct 12595 ms 249152 KB Output is correct
17 Correct 142 ms 249152 KB Output is correct
18 Correct 145 ms 249152 KB Output is correct
19 Correct 150 ms 249152 KB Output is correct
20 Correct 142 ms 249152 KB Output is correct
21 Correct 153 ms 249152 KB Output is correct
22 Correct 155 ms 249152 KB Output is correct
23 Correct 156 ms 249152 KB Output is correct
24 Correct 146 ms 249152 KB Output is correct
25 Correct 151 ms 249152 KB Output is correct
26 Correct 148 ms 249152 KB Output is correct
27 Correct 226 ms 249152 KB Output is correct
28 Correct 147 ms 249152 KB Output is correct
29 Correct 1284 ms 249152 KB Output is correct
30 Correct 3735 ms 253268 KB Output is correct
31 Correct 10448 ms 261384 KB Output is correct
32 Runtime error 9765 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.
33 Halted 0 ms 0 KB -