oj.uz

Submission #104928

# Submission time Handle Problem Language Result Execution time Memory
104928 2019-04-09T18:57:32 Z eriksuenderhauf Wombats (IOI13_wombats) C++11
76 / 100
 8058 ms 263168 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 = 2501;
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 + 8 >= 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 + 8 >= 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 16000 KB Output is correct
2 Correct 18 ms 16000 KB Output is correct
3 Correct 91 ms 17656 KB Output is correct
4 Correct 13 ms 16000 KB Output is correct
5 Correct 13 ms 16000 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 3 ms 640 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 79 ms 1528 KB Output is correct
12 Correct 2 ms 640 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 3260 KB Output is correct
2 Correct 588 ms 3240 KB Output is correct
3 Correct 561 ms 3260 KB Output is correct
4 Correct 610 ms 3260 KB Output is correct
5 Correct 515 ms 3240 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 432 KB Output is correct
9 Correct 2433 ms 3260 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 22 ms 25088 KB Output is correct
2 Correct 22 ms 25080 KB Output is correct
3 Correct 23 ms 25208 KB Output is correct
4 Correct 53 ms 25848 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 3328 KB Output is correct
2 Correct 499 ms 3320 KB Output is correct
3 Correct 495 ms 3292 KB Output is correct
4 Correct 511 ms 3320 KB Output is correct
5 Correct 544 ms 3192 KB Output is correct
6 Correct 23 ms 25088 KB Output is correct
7 Correct 22 ms 25088 KB Output is correct
8 Correct 23 ms 25140 KB Output is correct
9 Correct 52 ms 25976 KB Output is correct
10 Correct 14 ms 16000 KB Output is correct
11 Correct 14 ms 16000 KB Output is correct
12 Correct 73 ms 17512 KB Output is correct
13 Correct 15 ms 16000 KB Output is correct
14 Correct 15 ms 16000 KB Output is correct
15 Correct 2 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 2 ms 512 KB Output is correct
19 Correct 3 ms 512 KB Output is correct
20 Correct 3 ms 484 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 68 ms 1628 KB Output is correct
26 Correct 2 ms 512 KB Output is correct
27 Correct 2363 ms 3264 KB Output is correct
28 Correct 7139 ms 164912 KB Output is correct
29 Correct 6369 ms 97772 KB Output is correct
30 Correct 6706 ms 97608 KB Output is correct
31 Correct 7723 ms 165848 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 485 ms 3384 KB Output is correct
2 Correct 541 ms 3296 KB Output is correct
3 Correct 567 ms 3292 KB Output is correct
4 Correct 497 ms 3256 KB Output is correct
5 Correct 473 ms 3192 KB Output is correct
6 Correct 23 ms 25088 KB Output is correct
7 Correct 22 ms 25088 KB Output is correct
8 Correct 24 ms 25088 KB Output is correct
9 Correct 59 ms 25884 KB Output is correct
10 Correct 14 ms 16000 KB Output is correct
11 Correct 15 ms 16000 KB Output is correct
12 Correct 78 ms 17568 KB Output is correct
13 Correct 14 ms 16000 KB Output is correct
14 Correct 15 ms 16000 KB Output is correct
15 Runtime error 8058 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -