oj.uz

Submission #116128

# Submission time Handle Problem Language Result Execution time Memory
116128 2019-06-10T17:32:10 Z Bruteforceman Wombats (IOI13_wombats) C++11
100 / 100
 8511 ms 194828 KB 
#include "wombats.h"
#include "bits/stdc++.h"

using namespace std;
#define left lft 
#define right ryt
#define div damn

int t[505 * 2][205][205];
int R, C;
int H[5005][205];
int V[5005][205];
int dp[105][205][205];

const int inf = 1e9;
const int leaf = 10;

int start, div, node, left, right;

void solver(int b, int e, int from, int to) {
	if(b > e) return ;
	int mid = (b + e) >> 1;
	int opt = -1;
	int cost = inf;
	for(int i = from; i <= to; i++) {
		int sum = t[left][start][i] + V[div][i] + t[right][i][mid];
		if(sum < cost) {
			cost = sum;
			opt = i;
		} 
	}
	t[node][start][mid] = cost;
	solver(b, mid - 1, from, opt);
	solver(mid + 1, e, opt, to);
}

void transition(int c, int b, int e) {
	left = c << 1;
	right = left + 1;
	div = (b + e) >> 1;
	node = c;
	for(int i = 0; i < C; i++) {
		start = i;
		solver(0, C - 1, 0, C - 1);
	}
}

void solve(int c, int b, int e) {
	for(int x = 0; x < C; x++) {
		for(int j = 0; j < C; j++) {
			dp[0][x][j] = 0;
			for(int k = min(x, j); k < max(x, j); k++) {
				dp[0][x][j] += H[b][k]; 
			}
		}
	}
	for(int i = b + 1; i <= e; i++) {
		for(int x = 0; x < C; x++) {
			for(int j = 0; j < C; j++) {
				dp[i - b][x][j] = inf;
			}
			int sum = 0;
			int opt = inf;
			for(int j = 0; j < C; j++) {
				opt = min(opt, -sum + dp[i - b - 1][x][j] + V[i - 1][j]);
				dp[i - b][x][j] = min(dp[i - b][x][j], opt + sum);
				sum += H[i][j];
			}
			sum = 0;
			opt = inf;
			for(int j = C - 1; j >= 0; j--) {
				sum += H[i][j];
				opt = min(opt, -sum + dp[i - b - 1][x][j] + V[i - 1][j]);
				dp[i - b][x][j] = min(dp[i - b][x][j], opt + sum);
			}
		}
	}
	for(int i = 0; i < C; i++) {
		for(int j = 0; j < C; j++) {
			t[c][i][j] = dp[e - b][i][j];
		}
	}
}
void build(int c = 1, int b = 0, int e = R - 1) {
	if(b == e || ((c << 1) + 1) >= 1000) {
		solve(c, b, e);
		return ;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	build(l, b, m);
	build(r, m+1, e);
	transition(c, b, e);
}
void update(int x, int c = 1, int b = 0, int e = R - 1) {
	if(b == e || ((c << 1) + 1) >= 1000) {
		solve(c, b, e);
		return ;
	}
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) update(x, l, b, m);
	else update(x, r, m+1, e);
	transition(c, b, e);
} 



void init(int r, int c, int h[5000][200], int v[5000][200]) {
	R = r; C = c;
	for(int i = 0; i < R; i++) {
		for(int j = 0; j < C - 1; j++) {
			H[i][j] = h[i][j];
		}
	}
	for(int i = 0; i < R - 1; i++) {
		for(int j = 0; j < C; j++) {
			V[i][j] = v[i][j];
		}
	}
	build();
}

void changeH(int x, int y, int p) {
	H[x][y] = p;
	update(x);
}

void changeV(int x, int y, int p) {
    V[x][y] = p;
    update(x + 1);
}

int escape(int x, int y) {
    return t[1][x][y];
}

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 12800 KB Output is correct
2 Correct 13 ms 12672 KB Output is correct
3 Correct 74 ms 15480 KB Output is correct
4 Correct 12 ms 12676 KB Output is correct
5 Correct 36 ms 12664 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 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 1280 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 4 ms 1280 KB Output is correct
7 Correct 3 ms 1280 KB Output is correct
8 Correct 3 ms 1152 KB Output is correct
9 Correct 3 ms 1152 KB Output is correct
10 Correct 3 ms 1152 KB Output is correct
11 Correct 66 ms 3576 KB Output is correct
12 Correct 3 ms 1152 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 17408 KB Output is correct
2 Correct 188 ms 17272 KB Output is correct
3 Correct 224 ms 17528 KB Output is correct
4 Correct 220 ms 17528 KB Output is correct
5 Correct 230 ms 17404 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 891 ms 17528 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 20 ms 21496 KB Output is correct
2 Correct 20 ms 21504 KB Output is correct
3 Correct 21 ms 21504 KB Output is correct
4 Correct 53 ms 22776 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 17400 KB Output is correct
2 Correct 199 ms 17144 KB Output is correct
3 Correct 232 ms 17656 KB Output is correct
4 Correct 242 ms 17528 KB Output is correct
5 Correct 216 ms 17476 KB Output is correct
6 Correct 19 ms 21504 KB Output is correct
7 Correct 19 ms 21368 KB Output is correct
8 Correct 19 ms 21504 KB Output is correct
9 Correct 50 ms 22776 KB Output is correct
10 Correct 12 ms 12672 KB Output is correct
11 Correct 13 ms 12672 KB Output is correct
12 Correct 72 ms 15480 KB Output is correct
13 Correct 13 ms 12672 KB Output is correct
14 Correct 12 ms 12672 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 3 ms 1152 KB Output is correct
19 Correct 3 ms 1152 KB Output is correct
20 Correct 3 ms 1152 KB Output is correct
21 Correct 3 ms 1280 KB Output is correct
22 Correct 3 ms 1152 KB Output is correct
23 Correct 3 ms 1152 KB Output is correct
24 Correct 3 ms 1152 KB Output is correct
25 Correct 66 ms 3580 KB Output is correct
26 Correct 3 ms 1152 KB Output is correct
27 Correct 824 ms 17656 KB Output is correct
28 Correct 1821 ms 106060 KB Output is correct
29 Correct 1775 ms 102648 KB Output is correct
30 Correct 1974 ms 102508 KB Output is correct
31 Correct 1749 ms 107820 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 221 ms 17448 KB Output is correct
2 Correct 191 ms 17292 KB Output is correct
3 Correct 228 ms 17648 KB Output is correct
4 Correct 225 ms 17528 KB Output is correct
5 Correct 249 ms 17400 KB Output is correct
6 Correct 21 ms 21496 KB Output is correct
7 Correct 20 ms 21376 KB Output is correct
8 Correct 21 ms 21504 KB Output is correct
9 Correct 52 ms 22776 KB Output is correct
10 Correct 13 ms 12800 KB Output is correct
11 Correct 67 ms 12664 KB Output is correct
12 Correct 74 ms 15452 KB Output is correct
13 Correct 14 ms 12672 KB Output is correct
14 Correct 12 ms 12672 KB Output is correct
15 Correct 2240 ms 193688 KB Output is correct
16 Correct 8511 ms 194828 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 3 ms 1280 KB Output is correct
21 Correct 4 ms 1152 KB Output is correct
22 Correct 3 ms 1280 KB Output is correct
23 Correct 3 ms 1152 KB Output is correct
24 Correct 3 ms 1152 KB Output is correct
25 Correct 3 ms 1152 KB Output is correct
26 Correct 3 ms 1152 KB Output is correct
27 Correct 95 ms 3596 KB Output is correct
28 Correct 5 ms 1152 KB Output is correct
29 Correct 901 ms 17656 KB Output is correct
30 Correct 1801 ms 106108 KB Output is correct
31 Correct 7323 ms 192372 KB Output is correct
32 Correct 7362 ms 192276 KB Output is correct
33 Correct 1689 ms 102492 KB Output is correct
34 Correct 8080 ms 188356 KB Output is correct
35 Correct 1876 ms 102672 KB Output is correct
36 Correct 8080 ms 188340 KB Output is correct
37 Correct 1763 ms 107864 KB Output is correct
38 Correct 7288 ms 192964 KB Output is correct
39 Correct 2 ms 384 KB Output is correct
40 Correct 8403 ms 188488 KB Output is correct