제출 #104933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104933		eriksuenderhauf	웜뱃 (IOI13_wombats)	C++11	100 / 100	3853 ms	177788 KiB

wombats

#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 = 2005;
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], opt[200];

void merge(int cur) {
	for (int i = 0; i < C; i++) {
		opt[i] = 0;
		for (int j = 0; j < C; j++)
			dp[cur][i][j] = INF;
	}
	for (int i = C - 1; i > -C; i--) {
		for (int j = C + min(-i, 0) - 1; j >= max(-i, 0); j--) {
			int oL = 0, oR = C - 1;
			if (j != max(-i, 0))
				oL = opt[j - 1];
			if (j != C + min(-i, 0) - 1)
				oR = opt[j];
			for (int k = oL; k <= oR; k++) {
				if (dp[cur][j][i + j] > dp[L[cur]][j][k] + dp[R[cur]][k][i + j]) {
					dp[cur][j][i + j] = dp[L[cur]][j][k] + dp[R[cur]][k][i + j];
					opt[j] = k;
				}
			}
		}
	}
}
 
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 + 9 >= 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 + 9 >= 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];
}

컴파일 시 표준 에러 (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