oj.uz

Submission #104930

# Submission time Handle Problem Language Result Execution time Memory
104930 2019-04-09T19:00:43 Z eriksuenderhauf Wombats (IOI13_wombats) C++11
76 / 100
 20000 ms 177688 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 mergeOpt(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 merge(int cur) {
	for (int i = 0; i < C; i++)
		for (int j = 0; j < C; j++)
			dp[cur][i][j] = INF;
	for (int i = 0; i < C; i++)
		for (int j = 0; j < C; j++)
			for (int k = 0; k < C; k++)
				dp[cur][i][j] = min(dp[cur][i][j], dp[L[cur]][i][k] + dp[R[cur]][k][j]);
}
 
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 + 10 >= 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 + 10 >= 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 12 ms 12516 KB Output is correct
2 Correct 13 ms 12604 KB Output is correct
3 Correct 79 ms 14076 KB Output is correct
4 Correct 11 ms 12544 KB Output is correct
5 Correct 12 ms 12544 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 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 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 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 2 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 79 ms 1400 KB Output is correct
12 Correct 2 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 3380 KB Output is correct
2 Correct 458 ms 3232 KB Output is correct
3 Correct 607 ms 3320 KB Output is correct
4 Correct 517 ms 3192 KB Output is correct
5 Correct 494 ms 3196 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 512 KB Output is correct
9 Correct 2637 ms 3268 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 19 ms 21248 KB Output is correct
2 Correct 22 ms 21248 KB Output is correct
3 Correct 21 ms 21248 KB Output is correct
4 Correct 64 ms 22008 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 3320 KB Output is correct
2 Correct 533 ms 3320 KB Output is correct
3 Correct 579 ms 3300 KB Output is correct
4 Correct 506 ms 3260 KB Output is correct
5 Correct 448 ms 3200 KB Output is correct
6 Correct 19 ms 21120 KB Output is correct
7 Correct 25 ms 21120 KB Output is correct
8 Correct 20 ms 21120 KB Output is correct
9 Correct 57 ms 22008 KB Output is correct
10 Correct 12 ms 12544 KB Output is correct
11 Correct 12 ms 12544 KB Output is correct
12 Correct 109 ms 14176 KB Output is correct
13 Correct 13 ms 12544 KB Output is correct
14 Correct 15 ms 12544 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 4 ms 512 KB Output is correct
25 Correct 79 ms 1456 KB Output is correct
26 Correct 3 ms 508 KB Output is correct
27 Correct 2734 ms 3292 KB Output is correct
28 Correct 6043 ms 100420 KB Output is correct
29 Correct 5898 ms 97868 KB Output is correct
30 Correct 6026 ms 97620 KB Output is correct
31 Correct 6022 ms 101452 KB Output is correct
32 Correct 2 ms 384 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 3288 KB Output is correct
2 Correct 453 ms 3320 KB Output is correct
3 Correct 497 ms 3320 KB Output is correct
4 Correct 508 ms 3192 KB Output is correct
5 Correct 496 ms 3292 KB Output is correct
6 Correct 20 ms 21120 KB Output is correct
7 Correct 23 ms 21120 KB Output is correct
8 Correct 20 ms 21248 KB Output is correct
9 Correct 53 ms 21880 KB Output is correct
10 Correct 13 ms 12592 KB Output is correct
11 Correct 12 ms 12544 KB Output is correct
12 Correct 113 ms 14276 KB Output is correct
13 Correct 13 ms 12520 KB Output is correct
14 Correct 13 ms 12544 KB Output is correct
15 Correct 6038 ms 176264 KB Output is correct
16 Execution timed out 20044 ms 177688 KB Time limit exceeded
17 Halted 0 ms 0 KB -