oj.uz

Submission #104927

# Submission time Handle Problem Language Result Execution time Memory
104927 2019-04-09T18:53:05 Z eriksuenderhauf Wombats (IOI13_wombats) C++11
76 / 100
 7412 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 = 4005;
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];
 
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 + 5 >= 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 + 5 >= 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 18 ms 17028 KB Output is correct
2 Correct 16 ms 17024 KB Output is correct
3 Correct 93 ms 18572 KB Output is correct
4 Correct 15 ms 17024 KB Output is correct
5 Correct 16 ms 17024 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 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 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 508 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 74 ms 1528 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 492 ms 3740 KB Output is correct
2 Correct 506 ms 3704 KB Output is correct
3 Correct 617 ms 3932 KB Output is correct
4 Correct 512 ms 3960 KB Output is correct
5 Correct 529 ms 3876 KB Output is correct
6 Correct 3 ms 412 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2480 ms 3908 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 26368 KB Output is correct
2 Correct 26 ms 26416 KB Output is correct
3 Correct 25 ms 26368 KB Output is correct
4 Correct 58 ms 27128 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 3804 KB Output is correct
2 Correct 509 ms 3704 KB Output is correct
3 Correct 546 ms 3912 KB Output is correct
4 Correct 520 ms 3804 KB Output is correct
5 Correct 498 ms 3840 KB Output is correct
6 Correct 24 ms 26368 KB Output is correct
7 Correct 24 ms 26368 KB Output is correct
8 Correct 25 ms 26368 KB Output is correct
9 Correct 59 ms 27132 KB Output is correct
10 Correct 15 ms 16996 KB Output is correct
11 Correct 15 ms 17024 KB Output is correct
12 Correct 98 ms 18580 KB Output is correct
13 Correct 15 ms 17016 KB Output is correct
14 Correct 16 ms 17024 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 356 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 3 ms 512 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 3 ms 588 KB Output is correct
23 Correct 13 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 96 ms 1528 KB Output is correct
26 Correct 3 ms 540 KB Output is correct
27 Correct 2525 ms 3908 KB Output is correct
28 Correct 6804 ms 184600 KB Output is correct
29 Correct 6908 ms 181764 KB Output is correct
30 Correct 7121 ms 181688 KB Output is correct
31 Correct 7412 ms 185604 KB Output is correct
32 Correct 3 ms 384 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 3760 KB Output is correct
2 Correct 503 ms 3696 KB Output is correct
3 Correct 527 ms 3960 KB Output is correct
4 Correct 517 ms 3960 KB Output is correct
5 Correct 518 ms 3876 KB Output is correct
6 Correct 25 ms 26368 KB Output is correct
7 Correct 25 ms 26360 KB Output is correct
8 Correct 25 ms 26368 KB Output is correct
9 Correct 56 ms 27128 KB Output is correct
10 Correct 15 ms 16996 KB Output is correct
11 Correct 15 ms 17024 KB Output is correct
12 Correct 91 ms 18652 KB Output is correct
13 Correct 15 ms 17024 KB Output is correct
14 Correct 16 ms 17024 KB Output is correct
15 Runtime error 7004 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -