Submission #18472

#	Time	Username	Problem	Language	Result	Execution time	Memory
18472		eaststar	L 모양의 종이 자르기 (KOI15_cut)	C++14	25 / 25	172 ms	27520 KiB

cut

#include <stdio.h>
#include <algorithm>
using namespace std;
int D[51][51][51][51],E[51][51];
int g(int h,int w){
    int i,&s=E[h][w];
    if(s)return s;
    if(h==w)return s=1;
    s=1e4;
    for(i=1;i<h;++i)s=min(s,g(i,w)+g(h-i,w));
    for(i=1;i<w;++i)s=min(s,g(h,i)+g(h,w-i));
    return s;
}
int f(int h1,int w1,int h2,int w2){
    int i,&s=D[h1][w1][h2][w2];
    if(s)return s;
    s=1e4;
    for(i=1;i<h2;++i)s=min(s,g(i,w1-w2)+f(h1-i,w1,h2-i,w2));
    s=min(s,g(h2,w1-w2)+g(h1-h2,w1));
    for(++i;i<h1;++i)s=min(s,f(i,w1,h2,w2)+g(h1-i,w1));
    for(i=1;i<w2;++i)s=min(s,g(i,h1-h2)+f(w1-i,h1,w2-i,h2));
    s=min(s,g(w2,h1-h2)+g(w1-w2,h1));
    for(++i;i<w1;++i)s=min(s,f(i,h1,w2,h2)+g(w1-i,h1));
    return D[w1][h1][w2][h2]=s;
}
int main(){
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    printf("%d",f(a,b,c,d));
    return 0;
}

• Subtask 1: 25 / 25