제출 #134863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134863		mirbek01	웜뱃 (IOI13_wombats)	C++11	55 / 100	20055 ms	29932 KiB

wombats

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

using namespace std;

const int N = 5e3 + 5;
const int M = 202;

int v[N][M], h[N][M], dp[N][M], ans[M][M], r, c;

void build(){
	for(int x = 0; x < c; x ++){
		for(int i = 0; i < r; i ++)
			for(int j = 0; j < c; j ++)
				dp[i][j] = 2e9;
		set < pair <int, pair <int, int> > > st;
		dp[0][x] = 0;
		st.insert({0, {0, x}});
		while(!st.empty()){
			pair <int, int> y = st.begin()->second;
			st.erase(st.begin());
			if(y.second + 1 < c && dp[y.first][y.second + 1] > dp[y.first][y.second] + h[y.first][y.second]){
				st.erase( {dp[y.first][y.second + 1], {y.first, y.second + 1}} );
				dp[y.first][y.second + 1] = dp[y.first][y.second] + h[y.first][y.second];
				st.insert( {dp[y.first][y.second + 1], {y.first, y.second + 1}} );				 
			}
			if(y.second - 1 >= 0 && dp[y.first][y.second - 1] > dp[y.first][y.second] + h[y.first][y.second - 1]){
				st.erase( {dp[y.first][y.second - 1], {y.first, y.second - 1}} );
				dp[y.first][y.second - 1] = dp[y.first][y.second] + h[y.first][y.second - 1];
				st.insert( {dp[y.first][y.second - 1], {y.first, y.second - 1}} );				 
			}
			if(y.first + 1 < r && dp[y.first + 1][y.second] > dp[y.first][y.second] + v[y.first][y.second]){
				st.erase( {dp[y.first + 1][y.second], {y.first + 1, y.second}} );
				dp[y.first + 1][y.second] = dp[y.first][y.second] + v[y.first][y.second];
				st.insert( {dp[y.first + 1][y.second], {y.first + 1, y.second}} );				 
			}			
		}
		for(int y = 0; y < c; y ++)
			ans[x][y] = dp[r - 1][y];
	}
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
	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];
	r = R, c = C;
	if(c <= 2)
		build();
}

void changeH(int P, int Q, int W) {
	h[P][Q] = W;
	if(c <= 2)
		build();
}

void changeV(int P, int Q, int W) {
	v[P][Q] = W;
	if(c <= 2)
		build();
}

int escape(int x, int y) {
	if(c > 2){
		for(int i = 0; i < r; i ++)
			for(int j = 0; j < c; j ++)
				dp[i][j] = 2e9;
		set < pair <int, pair <int, int> > > st;
		dp[0][x] = 0;
		st.insert({0, {0, x}});
		while(!st.empty()){
			pair <int, int> y = st.begin()->second;
			st.erase(st.begin());
			if(y.second + 1 < c && dp[y.first][y.second + 1] > dp[y.first][y.second] + h[y.first][y.second]){
				st.erase( {dp[y.first][y.second + 1], {y.first, y.second + 1}} );
				dp[y.first][y.second + 1] = dp[y.first][y.second] + h[y.first][y.second];
				st.insert( {dp[y.first][y.second + 1], {y.first, y.second + 1}} );				 
			}
			if(y.second - 1 >= 0 && dp[y.first][y.second - 1] > dp[y.first][y.second] + h[y.first][y.second - 1]){
				st.erase( {dp[y.first][y.second - 1], {y.first, y.second - 1}} );
				dp[y.first][y.second - 1] = dp[y.first][y.second] + h[y.first][y.second - 1];
				st.insert( {dp[y.first][y.second - 1], {y.first, y.second - 1}} );				 
			}
			if(y.first + 1 < r && dp[y.first + 1][y.second] > dp[y.first][y.second] + v[y.first][y.second]){
				st.erase( {dp[y.first + 1][y.second], {y.first + 1, y.second}} );
				dp[y.first + 1][y.second] = dp[y.first][y.second] + v[y.first][y.second];
				st.insert( {dp[y.first + 1][y.second], {y.first + 1, y.second}} );				 
			}			
		}
		return dp[r - 1][y];
	} else{
		return ans[x][y];
	}
}

컴파일 시 표준 에러 (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: 0 / 21
• Subtask 6: 0 / 24