oj.uz

Submission #104923

# Submission time Handle Problem Language Result Execution time Memory
104923 2019-04-09T18:31:02 Z eriksuenderhauf Wombats (IOI13_wombats) C++11
55 / 100
 20000 ms 19948 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 = 20005;
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][100][100];

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 <= r + 5) {
		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 <= r + 5) {
		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 28 ms 8192 KB Output is correct
2 Correct 24 ms 8192 KB Output is correct
3 Correct 107 ms 9848 KB Output is correct
4 Correct 24 ms 8192 KB Output is correct
5 Correct 25 ms 8164 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 384 KB Output is correct
5 Correct 2 ms 384 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
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 83 ms 1400 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 666 ms 888 KB Output is correct
2 Correct 646 ms 768 KB Output is correct
3 Correct 677 ms 896 KB Output is correct
4 Correct 643 ms 760 KB Output is correct
5 Correct 624 ms 888 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
9 Correct 3287 ms 748 KB Output is correct
10 Correct 2 ms 428 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 16000 KB Output is correct
2 Correct 69 ms 15972 KB Output is correct
3 Correct 65 ms 16120 KB Output is correct
4 Correct 99 ms 16892 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 744 KB Output is correct
2 Correct 654 ms 768 KB Output is correct
3 Correct 665 ms 760 KB Output is correct
4 Correct 659 ms 860 KB Output is correct
5 Correct 624 ms 888 KB Output is correct
6 Correct 76 ms 16000 KB Output is correct
7 Correct 112 ms 16112 KB Output is correct
8 Correct 77 ms 16220 KB Output is correct
9 Correct 105 ms 16848 KB Output is correct
10 Correct 26 ms 8104 KB Output is correct
11 Correct 25 ms 8192 KB Output is correct
12 Correct 137 ms 9848 KB Output is correct
13 Correct 23 ms 8192 KB Output is correct
14 Correct 32 ms 8192 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 384 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 72 ms 1528 KB Output is correct
26 Correct 3 ms 428 KB Output is correct
27 Correct 3309 ms 828 KB Output is correct
28 Execution timed out 20051 ms 19948 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 760 KB Output is correct
2 Correct 649 ms 768 KB Output is correct
3 Correct 661 ms 752 KB Output is correct
4 Correct 641 ms 640 KB Output is correct
5 Correct 650 ms 748 KB Output is correct
6 Correct 82 ms 16000 KB Output is correct
7 Correct 71 ms 16064 KB Output is correct
8 Correct 74 ms 16000 KB Output is correct
9 Correct 107 ms 16736 KB Output is correct
10 Correct 23 ms 8192 KB Output is correct
11 Correct 20 ms 8192 KB Output is correct
12 Correct 77 ms 9724 KB Output is correct
13 Correct 19 ms 8192 KB Output is correct
14 Correct 19 ms 8192 KB Output is correct
15 Incorrect 6839 ms 16180 KB Output isn't correct
16 Halted 0 ms 0 KB -