oj.uz

Submission #98097

# Submission time Handle Problem Language Result Execution time Memory
98097 2019-02-20T16:24:26 Z tincamatei Wombats (IOI13_wombats) C++14
100 / 100
 10967 ms 187464 KB 
#include "wombats.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX_C = 200;
const int MAX_R = 5000;
const int INF = 1000000000;
 
int R, C;
int H[MAX_R][MAX_C], V[MAX_R][MAX_C];
int sp[MAX_R][MAX_C];
int a[MAX_C][MAX_C];
 
struct Matrix {
	int dp[MAX_C][MAX_C];
	Matrix() {
		for(int i = 0; i < MAX_C; ++i)
			for(int j = 0; j < MAX_C; ++j)
				dp[i][j] = INF;
	}
 
	Matrix operator* (const Matrix &x) const {
		Matrix rez;
		for(int i = 0; i < C; ++i) {
			for(int j = 0; j < C; ++j) {
				int dist = dp[i][j] + x.dp[j][i];
				if(dist < rez.dp[i][i]) {
					rez.dp[i][i] = dist;
					a[i][i] = j;
				}
			}
		}
 
		for(int d = 1; d < C; ++d) {
			for(int i = 0; i < C - d; ++i) {
				int j = i + d;
				int st, dr;
				st = a[i][j - 1];
				dr = a[i + 1][j];
				for(int k = st; k <= dr; ++k) {
					int dist = dp[i][k] + x.dp[k][j];
					if(dist < rez.dp[i][j]) {
						rez.dp[i][j] = dist;
						a[i][j] = k;
					}
				}
			}
 
			for(int i = d; i < C; ++i) {
				int j = i - d;
				int st, dr;
				st = a[i - 1][j];
				dr = a[i][j + 1];
				for(int k = st; k <= dr; ++k) {
					int dist = dp[i][k] + x.dp[k][j];
					if(dist < rez.dp[i][j]) {
						rez.dp[i][j] = dist;
						a[i][j] = k;
					}
				}
			}
		}
		return rez;
	}
} aint[1000];

Matrix rez;

void initzero(Matrix &x) {
	for(int i = 0; i < C; ++i)
		for(int j = 0; j < C; ++j)
			if(i == j)
				x.dp[i][j] = 0;
			else
				x.dp[i][j] = INF;
}
 
void initrow(Matrix &x, int r) {
	for(int i = 0; i < C; ++i)
		for(int j = 0; j < C; ++j)
			x.dp[i][j] = abs(sp[r][i] - sp[r][j]) + V[r][j];
}
 
void updRange(Matrix &x, int l, int r) {
	initzero(x);
	for(int i = l; i <= r; ++i) {
		Matrix y;
		initrow(y, i);
		x = x * y;
	}
}

void initSegTree(int l, int r, int nod = 1) {
	if(r - l + 1 <= 20)
		updRange(aint[nod], l, r);
	else {
		int mid = (l + r) / 2;
		initSegTree(l, mid, 2 * nod);
		initSegTree(mid + 1, r, 2 * nod + 1);
		aint[nod] = aint[2 * nod] * aint[2 * nod + 1];
	}
}

void updPoint(int poz, int l, int r, int nod = 1) {
	if(poz < l || r < poz) return;
	if(r - l + 1 <= 20)
		updRange(aint[nod], l, r);
	else {
		int mid = (l + r) / 2;
		updPoint(poz, l, mid, 2 * nod);
		updPoint(poz, mid + 1, r, 2 * nod + 1);
		aint[nod] = aint[2 * nod] * aint[2 * nod + 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) {
		sp[i][0] = 0;
		for(int j = 1; j < C; ++j)
			sp[i][j] = sp[i][j - 1] + H[i][j - 1];
	}
 
	initSegTree(0, R - 1);
}
 
void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	for(int i = 1; i < C; ++i)
		sp[P][i] = sp[P][i - 1] + H[P][i - 1];
	updPoint(P, 0, R - 1);
}
 
void changeV(int P, int Q, int W) {
	V[P][Q] = W;
	updPoint(P, 0, R - 1);
}
 
int escape(int V1, int V2) {
	return aint[1].dp[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 1244 ms 174360 KB Output is correct
2 Correct 1247 ms 174360 KB Output is correct
3 Correct 1312 ms 175864 KB Output is correct
4 Correct 1191 ms 174400 KB Output is correct
5 Correct 1213 ms 174364 KB Output is correct
6 Correct 158 ms 157432 KB Output is correct
7 Correct 133 ms 157428 KB Output is correct
8 Correct 132 ms 157404 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 157440 KB Output is correct
2 Correct 140 ms 157396 KB Output is correct
3 Correct 145 ms 157308 KB Output is correct
4 Correct 138 ms 157408 KB Output is correct
5 Correct 133 ms 157432 KB Output is correct
6 Correct 147 ms 157500 KB Output is correct
7 Correct 152 ms 157456 KB Output is correct
8 Correct 143 ms 157604 KB Output is correct
9 Correct 128 ms 157444 KB Output is correct
10 Correct 132 ms 157500 KB Output is correct
11 Correct 281 ms 158508 KB Output is correct
12 Correct 148 ms 157580 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 158476 KB Output is correct
2 Correct 310 ms 158328 KB Output is correct
3 Correct 450 ms 158456 KB Output is correct
4 Correct 451 ms 158384 KB Output is correct
5 Correct 410 ms 158328 KB Output is correct
6 Correct 142 ms 157432 KB Output is correct
7 Correct 139 ms 157432 KB Output is correct
8 Correct 132 ms 157432 KB Output is correct
9 Correct 1337 ms 158328 KB Output is correct
10 Correct 144 ms 157432 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1272 ms 178276 KB Output is correct
2 Correct 1176 ms 178424 KB Output is correct
3 Correct 1447 ms 178420 KB Output is correct
4 Correct 1187 ms 179136 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 158388 KB Output is correct
2 Correct 390 ms 158456 KB Output is correct
3 Correct 436 ms 158368 KB Output is correct
4 Correct 425 ms 158328 KB Output is correct
5 Correct 387 ms 158456 KB Output is correct
6 Correct 1172 ms 178384 KB Output is correct
7 Correct 1264 ms 178296 KB Output is correct
8 Correct 1249 ms 178244 KB Output is correct
9 Correct 1411 ms 178936 KB Output is correct
10 Correct 1135 ms 174328 KB Output is correct
11 Correct 1201 ms 174328 KB Output is correct
12 Correct 1312 ms 175920 KB Output is correct
13 Correct 1296 ms 174368 KB Output is correct
14 Correct 1363 ms 174400 KB Output is correct
15 Correct 145 ms 157436 KB Output is correct
16 Correct 148 ms 157436 KB Output is correct
17 Correct 139 ms 157304 KB Output is correct
18 Correct 154 ms 157428 KB Output is correct
19 Correct 140 ms 157468 KB Output is correct
20 Correct 147 ms 157444 KB Output is correct
21 Correct 135 ms 157404 KB Output is correct
22 Correct 144 ms 157432 KB Output is correct
23 Correct 154 ms 157424 KB Output is correct
24 Correct 130 ms 157516 KB Output is correct
25 Correct 281 ms 158556 KB Output is correct
26 Correct 161 ms 157432 KB Output is correct
27 Correct 1423 ms 158320 KB Output is correct
28 Correct 2929 ms 178660 KB Output is correct
29 Correct 3091 ms 175224 KB Output is correct
30 Correct 3277 ms 175216 KB Output is correct
31 Correct 2981 ms 179920 KB Output is correct
32 Correct 137 ms 157432 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 158312 KB Output is correct
2 Correct 349 ms 158324 KB Output is correct
3 Correct 543 ms 158328 KB Output is correct
4 Correct 458 ms 158448 KB Output is correct
5 Correct 434 ms 158328 KB Output is correct
6 Correct 1240 ms 178168 KB Output is correct
7 Correct 1192 ms 178168 KB Output is correct
8 Correct 1163 ms 178192 KB Output is correct
9 Correct 1355 ms 179044 KB Output is correct
10 Correct 1197 ms 174512 KB Output is correct
11 Correct 1331 ms 174328 KB Output is correct
12 Correct 1376 ms 175948 KB Output is correct
13 Correct 1237 ms 174308 KB Output is correct
14 Correct 1203 ms 174260 KB Output is correct
15 Correct 2720 ms 178452 KB Output is correct
16 Correct 10967 ms 180932 KB Output is correct
17 Correct 136 ms 157304 KB Output is correct
18 Correct 148 ms 157312 KB Output is correct
19 Correct 143 ms 157432 KB Output is correct
20 Correct 151 ms 157560 KB Output is correct
21 Correct 161 ms 157432 KB Output is correct
22 Correct 147 ms 157432 KB Output is correct
23 Correct 148 ms 157532 KB Output is correct
24 Correct 153 ms 157432 KB Output is correct
25 Correct 147 ms 157476 KB Output is correct
26 Correct 169 ms 157488 KB Output is correct
27 Correct 271 ms 159960 KB Output is correct
28 Correct 153 ms 157548 KB Output is correct
29 Correct 1334 ms 158444 KB Output is correct
30 Correct 3055 ms 182556 KB Output is correct
31 Correct 8894 ms 187064 KB Output is correct
32 Correct 8375 ms 186880 KB Output is correct
33 Correct 3086 ms 178916 KB Output is correct
34 Correct 9471 ms 182800 KB Output is correct
35 Correct 3022 ms 178688 KB Output is correct
36 Correct 9193 ms 182856 KB Output is correct
37 Correct 2900 ms 184332 KB Output is correct
38 Correct 9155 ms 187464 KB Output is correct
39 Correct 136 ms 157432 KB Output is correct
40 Correct 9029 ms 183000 KB Output is correct