Submission #437486

#	Time	Username	Problem	Language	Result	Execution time	Memory
437486		denverjin	Wombats (IOI13_wombats)	C++14	100 / 100	14037 ms	179896 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>

#define eprintf(args...) fprintf(stderr, args)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

const int mxn = 1 << 13;
int R, C;
int H[5000][200];
int V[5000][200];

struct O_o {
	int l, r;
	int dp[200][200];

	O_o() { l = r = -1; memset(dp, 0x3f, sizeof(dp)); }
};

O_o operator + (const O_o &A, const O_o &B) {
	if (A.l == -1) return B;
	if (B.l == -1) return A;
	O_o ans;
	ans.l = A.l, ans.r = B.r;
	static int pr[205][205];
	rep(i, C) rep(j, C) pr[i][j] = -1;
	for (int delta = -(C - 1); delta <= (C - 1); ++ delta) {
		for (int a = 0; a < C; ++ a) {
			int b = a + delta;
			if (b >= 0 && b < C) {
				int L = b ? pr[a][b - 1] : 0;
				int R = a + 1 < C ? pr[a + 1][b] : C - 1;
				for (int c = L; c <= R; ++ c) {
					if (ans.dp[a][b] > A.dp[a][c] + B.dp[c][b]) {
						ans.dp[a][b] = A.dp[a][c] + B.dp[c][b];
						pr[a][b] = c;
					}
				}
			}
		}
	}
	return ans;
}

const int b = 4, B = 1 << b;

O_o S[mxn >> (b - 1)];

O_o get(int i) {
	if (i + 1 >= R) return O_o();
	O_o ans;
	ans.l = i; ans.r = i + 1;
	static int sum[2][200];
	rep(c, 2) {
		sum[c][0] = 0;
		rep(j, C - 1) sum[c][j + 1] = sum[c][j] + H[i + c][j];
	}
	for (int a = 0; a < C; ++ a) {
		int mn = 0x3f3f3f3f;
		for (int b = a; b < C; ++ b) {
			mn = std::min(mn, sum[0][b] - sum[0][a] + V[i][b] - sum[1][b]);
			ans.dp[a][b] = std::min(ans.dp[a][b], mn + sum[1][b]);
		}
		mn = 0x3f3f3f3f;
		for (int b = 0; b < C; ++ b) {
			if (b <= a) mn = std::min(mn, sum[0][a] - sum[0][b] + V[i][b] - sum[1][b]);
			ans.dp[a][b] = std::min(ans.dp[a][b], mn + sum[1][b]);
		}
		mn = 0x3f3f3f3f;
		for (int b = a; b >= 0; -- b) {
			mn = std::min(mn, sum[0][a] - sum[0][b] + V[i][b] + sum[1][b]);
			ans.dp[a][b] = std::min(ans.dp[a][b], mn - sum[1][b]);
		}
		mn = 0x3f3f3f3f;
		for (int b = C - 1; b >= 0; -- b) {
			if (b >= a) mn = std::min(mn, sum[0][b] - sum[0][a] + V[i][b] + sum[1][b]);
			ans.dp[a][b] = std::min(ans.dp[a][b], mn - sum[1][b]);
		}
	}
	return ans;
}

void update(int i) {
	O_o ans;
	for (int j = i; j < i + B; ++ j)
		ans = ans + get(j);
	S[(i >> b) + (mxn >> b)] = ans;
	for (int x = (i >> b) + (mxn >> b); x >>= 1; ) {
		S[x] = S[x << 1] + S[x << 1 | 1];
	}
}

void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
	R = _R;
	C = _C;
	memcpy(H, _H, sizeof(H));
	memcpy(V, _V, sizeof(V));
	for (int i = 0; i << b < R; ++ i) update(i << b);
}

void changeH(int P, int Q, int W) {
	H[P][Q] = W;
	if (P && ((P - 1) >> b) != (P >> b)) update((P - 1) >> b << b);
	update(P >> b << b);
}

void changeV(int P, int Q, int W) {
	V[P][Q] = W;
	update(P >> b << b);
	if ((P >> b) != ((P + 1) >> b)) update((P + 1) >> b << b);
}

int escape(int V1, int V2) {
	return S[1].dp[V1][V2];
}

#ifdef DEBUG
#include "grader.c"
#endif

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  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