제출 #280416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
280416		Saboon	웜뱃 (IOI13_wombats)	C++14	100 / 100	7162 ms	135000 KiB

wombats

#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int T = 20;
int M, R, C, H[5000][200], V[5000][200];
int bl[255][200][200], dp[1026][200][200], opt[200][200];

void change(int id, int L, int R, int idx){
	if (idx < L or R <= idx)
		return;
	if (L + 1 == R){
		for (int i = 0; i < C; i++)
			for (int j = 0; j < C; j++)
				dp[id][i][j] = bl[L][i][j];
		return;
	}
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, idx);
	change(2*id+1, mid, R, idx);
	for (int i = 0; i < C; i++){
		for (int j = C-1; j >= 0; j--){
			int lo = 0, hi = C-1;
			if (j+1 < C)
				hi = opt[i][j+1];
			if (i > 0)
				lo = opt[i-1][j];
			dp[id][i][j] = inf;
			for (int x = lo; x <= hi; x++){
				if (dp[id][i][j] > dp[2*id+0][i][x] + dp[2*id+1][x][j]){
					dp[id][i][j] = dp[2*id+0][i][x] + dp[2*id+1][x][j];
					opt[i][j] = x;
				}
			}
		}
	}
}

void ChangeBlock(int block){
	for (int j = 0; j < C; j++){
		for (int k = 0; k < C; k++)
			bl[block][j][k] = inf;
		bl[block][j][j] = 0;
		for (int k = j+1; k < C; k++)
			bl[block][j][k] = bl[block][j][k-1] + H[T*block][k-1];
		for (int k = j-1; k >= 0; k--)
			bl[block][j][k] = bl[block][j][k+1] + H[T*block][k];
		for (int k = 0; k < C; k++)
			bl[block][j][k] += V[T*block][k];
		for (int i = T*block+1; i < min(R, T*(block+1)); i++){
			for (int k = 1; k < C; k++)
				bl[block][j][k] = min(bl[block][j][k], bl[block][j][k-1] + H[i][k-1]);
			for (int k = C-2; k >= 0; k--)
				bl[block][j][k] = min(bl[block][j][k], bl[block][j][k+1] + H[i][k]);
			for (int k = 0; k < C; k++)
				bl[block][j][k] += V[i][k];
		}
	}
}
 
void init(int r, int c, int h[5000][200], int v[5000][200]){
	M = (r-1)/T + 1;
	R = r, C = c;
	for (int i = 0; i < 5000; i++)
		for (int j = 0; j < 200; j++)
			H[i][j] = h[i][j], V[i][j] = v[i][j];
	for (int i = 0; i < R; i += T)
		ChangeBlock(i/T);
	for (int i = 0; i < M; i++)
		change(1, 0, M, i);	
}
 
void changeH(int P, int Q, int W){
	H[P][Q] = W;
	ChangeBlock(P/T);
	change(1, 0, M, P/T);
}
 
void changeV(int P, int Q, int W){
	V[P][Q] = W;
	ChangeBlock(P/T);
	change(1, 0, M, P/T);
}
 
int escape(int V1, int V2){
	return dp[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;
      |      ^~~

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