Submission #18089

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
18089	2016-01-20T05:36:38 Z	comet	L 모양의 종이 자르기 (KOI15_cut)	C++	25 / 25	244 ms	27508 KB

cut

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int dp[51][51][51][51];

int f(int N,int M,int x,int y){
	if(x==0||y==0)x=y=0;
	if(x==0&&y==0){
		if(N==1)return M;
		if(M==1)return N;
		if(N==M)return 1;
	}
	// if(x==N&&y==M)return 0;
	int& ret=dp[N][M][x][y];
	if(~ret)return ret;
	ret=1e9;
	// y-axis
	for(int i=1;i<=x;i++){
		ret=min(ret,f(i,M-y,0,0)+f(N-i,M,x-i,y));
	}
	for(int i=x+1;i<N;i++){
		ret=min(ret,f(i,M,x,y)+f(N-i,M,0,0));
	}
	// x-axis
	for(int i=1;i<M-y;i++){
		ret=min(ret,f(N,i,0,0)+f(N,M-i,x,y));
	}
	for(int i=M-y;i<M;i++){
		ret=min(ret,f(N,i,x,i-(M-y))+f(N-x,M-i,0,0));
	}
	return ret;
}

int main(){
	memset(dp,-1,sizeof(dp));
	int N,M,x,y;
	scanf("%d%d%d%d",&N,&M,&x,&y);
	printf("%d\n",f(N,M,x,y));
}

Subtask #1

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	27508 KB	Output is correct
2	Correct	14 ms	27508 KB	Output is correct
3	Correct	17 ms	27508 KB	Output is correct
4	Correct	235 ms	27508 KB	Output is correct
5	Correct	17 ms	27508 KB	Output is correct
6	Correct	3 ms	27508 KB	Output is correct
7	Correct	0 ms	27508 KB	Output is correct
8	Correct	0 ms	27508 KB	Output is correct
9	Correct	0 ms	27508 KB	Output is correct
10	Correct	3 ms	27508 KB	Output is correct
11	Correct	20 ms	27508 KB	Output is correct
12	Correct	6 ms	27508 KB	Output is correct
13	Correct	6 ms	27508 KB	Output is correct
14	Correct	25 ms	27508 KB	Output is correct
15	Correct	19 ms	27508 KB	Output is correct
16	Correct	244 ms	27508 KB	Output is correct
17	Correct	10 ms	27508 KB	Output is correct
18	Correct	68 ms	27508 KB	Output is correct
19	Correct	23 ms	27508 KB	Output is correct
20	Correct	3 ms	27508 KB	Output is correct