Submission #116128

#	Time	Username	Problem	Language	Result	Execution time	Memory
116128		Bruteforceman	Wombats (IOI13_wombats)	C++11	100 / 100	8511 ms	194828 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24