oj.uz

Submission #104934

# Submission time Handle Problem Language Result Execution time Memory
104934 2019-04-09T19:08:59 Z eriksuenderhauf Wombats (IOI13_wombats) C++11
100 / 100
 5430 ms 177924 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "wombats.h"
//#include "grader.h"
using namespace std;
typedef long long int ll;
const int INF = 1e9 + 7;
const int MAXN = 2005;
const double eps = 1e-9;
int RW, C, root = 0, segSz = 1;
int h[5000][200], v[5000][200], L[MAXN], R[MAXN];
int dp[MAXN][200][200], opt[200];

void merge(int cur) {
	for (int i = 0; i < C; i++) {
		opt[i] = 0;
		for (int j = 0; j < C; j++)
			dp[cur][i][j] = INF;
	}
	for (int i = C - 1; i > -C; i--) {
		for (int j = C + min(-i, 0) - 1; j >= max(-i, 0); j--) {
			int oL = 0, oR = C - 1;
			if (j != max(-i, 0))
				oL = opt[j - 1];
			if (j != C + min(-i, 0) - 1)
				oR = opt[j];
			for (int k = oL; k <= oR; k++) {
				if (dp[cur][j][i + j] > dp[L[cur]][j][k] + dp[R[cur]][k][i + j]) {
					dp[cur][j][i + j] = dp[L[cur]][j][k] + dp[R[cur]][k][i + j];
					opt[j] = k;
				}
			}
		}
	}
}
 
void init(int cur, int l, int r) {
	for (int i = 0; i < C; i++) {
		for (int j = 0; j < C; j++)
			dp[cur][i][j] = INF;
		dp[cur][i][i] = 0;
	}
	for (int k = l; k <= r; k++) {
		for (int i = 0; i < C; i++) {
			for (int j = 1; j < C; j++)
				dp[cur][i][j] = min(dp[cur][i][j], dp[cur][i][j - 1] + h[k][j - 1]);
			for (int j = C - 2; j > -1; j--)
				dp[cur][i][j] = min(dp[cur][i][j], dp[cur][i][j + 1] + h[k][j]);
		}
		for (int i = 0; i < C; i++)
			for (int j = 0; j < C; j++)
				dp[cur][i][j] += v[k][j];
	}
}
 
void upd(int l, int r, int cur, int ind) {
	if (l + 9 >= r) {
		init(cur, l, r);
		return;
	}
	int m = (l + r) / 2;
	if (ind <= m) upd(l, m, L[cur], ind);
	else upd(m + 1, r, R[cur], ind);
	merge(cur);
}
 
void build(int l, int r, int &cur) {
	cur = segSz++;
	if (l + 9 >= r) {
		init(cur, l, r);
		return;
	}
	int m = (l + r) / 2;
	build(l, m, L[cur]);
	build(m + 1, r, R[cur]);
	merge(cur);
}
 
void init(int R1, int C1, int H[5000][200], int V[5000][200]) {
	RW = R1, C = C1;
	for (int i = 0; i < RW; i++)
		for (int j = 0; j + 1 < C; j++)
			h[i][j] = H[i][j];
	for (int i = 0; i + 1 < RW; i++)
		for (int j = 0; j < C; j++)
			v[i][j] = V[i][j];
	build(0, RW - 1, root);
}
 
void changeH(int p, int q, int w) {
	h[p][q] = w;
	upd(0, RW - 1, root, p);
}
 
void changeV(int p, int q, int w) {
	v[p][q] = w;
	upd(0, RW - 1, root, p);
}
 
int escape(int a, int b) {
	return dp[root][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;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12544 KB Output is correct
2 Correct 14 ms 12544 KB Output is correct
3 Correct 103 ms 14156 KB Output is correct
4 Correct 15 ms 12544 KB Output is correct
5 Correct 15 ms 12544 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 3200 KB Output is correct
2 Correct 90 ms 3200 KB Output is correct
3 Correct 114 ms 3264 KB Output is correct
4 Correct 106 ms 3272 KB Output is correct
5 Correct 105 ms 3280 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 451 ms 3200 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21248 KB Output is correct
2 Correct 21 ms 21096 KB Output is correct
3 Correct 25 ms 21120 KB Output is correct
4 Correct 69 ms 21980 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 3268 KB Output is correct
2 Correct 94 ms 3200 KB Output is correct
3 Correct 112 ms 3200 KB Output is correct
4 Correct 127 ms 3380 KB Output is correct
5 Correct 107 ms 3280 KB Output is correct
6 Correct 20 ms 21240 KB Output is correct
7 Correct 21 ms 21120 KB Output is correct
8 Correct 22 ms 21212 KB Output is correct
9 Correct 58 ms 21884 KB Output is correct
10 Correct 12 ms 12544 KB Output is correct
11 Correct 12 ms 12544 KB Output is correct
12 Correct 103 ms 14240 KB Output is correct
13 Correct 14 ms 12544 KB Output is correct
14 Correct 12 ms 12544 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 3 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 85 ms 1484 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 428 ms 3304 KB Output is correct
28 Correct 1501 ms 100576 KB Output is correct
29 Correct 1343 ms 97740 KB Output is correct
30 Correct 1349 ms 97660 KB Output is correct
31 Correct 1477 ms 101572 KB Output is correct
32 Correct 2 ms 384 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 3200 KB Output is correct
2 Correct 88 ms 3200 KB Output is correct
3 Correct 110 ms 3320 KB Output is correct
4 Correct 136 ms 3320 KB Output is correct
5 Correct 116 ms 3244 KB Output is correct
6 Correct 20 ms 21116 KB Output is correct
7 Correct 19 ms 21120 KB Output is correct
8 Correct 25 ms 21216 KB Output is correct
9 Correct 51 ms 22008 KB Output is correct
10 Correct 12 ms 12544 KB Output is correct
11 Correct 15 ms 12540 KB Output is correct
12 Correct 71 ms 14172 KB Output is correct
13 Correct 12 ms 12544 KB Output is correct
14 Correct 12 ms 12544 KB Output is correct
15 Correct 1924 ms 176212 KB Output is correct
16 Correct 5430 ms 177924 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 2 ms 512 KB Output is correct
26 Correct 3 ms 512 KB Output is correct
27 Correct 83 ms 1528 KB Output is correct
28 Correct 3 ms 512 KB Output is correct
29 Correct 411 ms 3200 KB Output is correct
30 Correct 1432 ms 100524 KB Output is correct
31 Correct 5213 ms 176980 KB Output is correct
32 Correct 5216 ms 176920 KB Output is correct
33 Correct 1302 ms 97744 KB Output is correct
34 Correct 4691 ms 174284 KB Output is correct
35 Correct 1533 ms 97644 KB Output is correct
36 Correct 4954 ms 174168 KB Output is correct
37 Correct 1415 ms 101432 KB Output is correct
38 Correct 5251 ms 177604 KB Output is correct
39 Correct 3 ms 384 KB Output is correct
40 Correct 5101 ms 174212 KB Output is correct