oj.uz

답안 #18030

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18030 2016-01-18T13:15:30 Z gs13068 L 모양의 종이 자르기 (KOI15_cut) C++
25 / 25
 378 ms 36840 KB 
#include<cstdio>
#include<algorithm>

int c[55][55];
int d[55][55][55][55];

int main()
{
    int i,j,k,l,t,w,x,y,z;
    scanf("%d%d%d%d",&w,&x,&y,&z);
    for(i=1;i<=w;i++)for(j=1;j<=x;j++)
	{
		c[i][j]=1e9;
		if(i==j)c[i][j]=1;
		for(k=1;k<i;k++)c[i][j]=std::min(c[i][j],c[k][j]+c[i-k][j]);
		for(l=1;l<j;l++)c[i][j]=std::min(c[i][j],c[i][l]+c[i][j-l]);
	}
	for(i=2;i<=w;i++)for(j=2;j<=x;j++)for(k=1;k<i;k++)for(l=1;l<j;l++)
	{
		d[i][j][k][l]=1e9;
		for(t=1;t<k;t++)d[i][j][k][l]=std::min(d[i][j][k][l],d[i-t][j][k-t][l]+c[t][j-l]);
		d[i][j][k][l]=std::min(d[i][j][k][l],c[k][j-l]+c[i-k][j]);
		for(t=k+1;t<i;t++)d[i][j][k][l]=std::min(d[i][j][k][l],d[t][j][k][l]+c[i-t][j]);
		for(t=1;t<l;t++)d[i][j][k][l]=std::min(d[i][j][k][l],d[i][j-t][k][l-t]+c[i-k][t]);
		d[i][j][k][l]=std::min(d[i][j][k][l],c[i-k][l]+c[i][j-l]);
		for(t=l+1;t<j;t++)d[i][j][k][l]=std::min(d[i][j][k][l],d[i][t][k][l]+c[i][j-t]);
	}
    printf("%d\n",d[w][x][y][z]);
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 36840 KB Output is correct
2 Correct 75 ms 36840 KB Output is correct
3 Correct 378 ms 36840 KB Output is correct
4 Correct 299 ms 36840 KB Output is correct
5 Correct 370 ms 36840 KB Output is correct
6 Correct 0 ms 36840 KB Output is correct
7 Correct 0 ms 36840 KB Output is correct
8 Correct 0 ms 36840 KB Output is correct
9 Correct 0 ms 36840 KB Output is correct
10 Correct 0 ms 36840 KB Output is correct
11 Correct 351 ms 36840 KB Output is correct
12 Correct 8 ms 36840 KB Output is correct
13 Correct 3 ms 36840 KB Output is correct
14 Correct 82 ms 36840 KB Output is correct
15 Correct 35 ms 36840 KB Output is correct
16 Correct 255 ms 36840 KB Output is correct
17 Correct 259 ms 36840 KB Output is correct
18 Correct 114 ms 36840 KB Output is correct
19 Correct 36 ms 36840 KB Output is correct
20 Correct 373 ms 36840 KB Output is correct