제출 #437445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437445		Eric_hoo	웜뱃 (IOI13_wombats)	C++14	0 / 100	151 ms	21068 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 2000000000;

int A[5000][200], B[5000][200];
int dp[10][200][200];
int cho[200][200];
int n, m;
int tmp[200][200];

void Merge(int f[200][200], int g[200][200], int wei[200], int h[200][200]) {
	for (int i = m - 1; i >= 0; i--) {
		for (int j = 0; j < m; j++) {
			int r = i + 1 < m ? cho[i + 1][j] : m - 1, l = j ? cho[i][j - 1] : 0;
			tmp[i][j] = INF;
			for (int k = l; k <= r; k++) {
				if (tmp[i][j] > f[i][k] + wei[k] + g[k][j]) {
					tmp[i][j] = f[i][k] + wei[k] + g[k][j];
					cho[i][j] = k;
				}
			}
		}
	}
	for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) h[i][j] = tmp[i][j];
}

struct Segment_tree {
	int T[1024][200][200];
	void Calc(int now, int l, int r) {
		int W = min(10, n - l * 10);
		for (int i = 0; i < W; i++) {
			for (int j = 0; j < m; j++) {
				dp[i][j][j] = 0;
				for (int k = j - 1; k >= 0; k--) dp[i][j][k] = dp[i][j][k + 1] + A[l * 10 + i][k];
				for (int k = j + 1; k < m; k++) dp[i][j][k] = dp[i][j][k - 1] + A[l * 10 + i][k - 1];
			}
		}
		for (int j = 0; j < m; j++) for (int k = 0; k < m; k++) T[now][j][k] = dp[0][j][k];
		for (int i = 1; i < W; i++) Merge(T[now], dp[i], B[l * 10 + i - 1], T[now]);
	}
	void Build(int now, int l, int r) {
		if (l == r) {
			Calc(now, l, r);
			return ;
		}
		int mid = l + r >> 1;
		Build(now << 1, l, mid), Build(now << 1 | 1, mid + 1, r);
		Merge(T[now << 1], T[now << 1 | 1], B[mid], T[now]); 
	}
	void Update(int now, int l, int r, int pos) {
		if (l == r) {
			Calc(now, l, r);
			return ; 
		}
		int mid = l + r >> 1;
		if (pos <= mid) Update(now << 1, l, mid, pos);
		else Update(now << 1 | 1, mid + 1, r, pos);
		Merge(T[now << 1], T[now << 1 | 1], B[mid], T[now]);
	}
}seg;

void init(int N, int M, int h[5000][200], int v[5000][200]) {
	n = N, m = M;
	for (int i = 0; i < n; i++) for (int j = 0; j + 1 < m; j++) A[i][j] = h[i][j];
	for (int i = 0; i + 1 < n; i++) for (int j = 0; j < m; j++) B[i][j] = v[i][j];
	seg.Build(1, 0, (n - 1) / 10);
}

void changeH(int P, int Q, int W) {
	A[P][Q] = W, seg.Update(1, 0, (n - 1) / 10, P / 10);
}

void changeV(int P, int Q, int W) {
	B[P][Q] = W;
	seg.Update(1, 0, (n - 1) / 10, P / 10);
	if ((P + 1) / 10 != P / 10) seg.Update(1, 0, (n - 1) / 10, (P + 1) / 10);
}

int escape(int V1, int V2) {
	return seg.T[1][V1][V2];
}

컴파일 시 표준 에러 (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;
      |      ^~~
wombats.cpp: In member function 'void Segment_tree::Build(int, int, int)':
wombats.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid = l + r >> 1;
      |             ~~^~~
wombats.cpp: In member function 'void Segment_tree::Update(int, int, int, int)':
wombats.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int mid = l + r >> 1;
      |             ~~^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24