Submission #18472

# Submission time Handle Problem Language Result Execution time Memory
18472 2016-02-05T13:31:33 Z eaststar L 모양의 종이 자르기 (KOI15_cut) C++14
25 / 25
172 ms 27520 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 61 ms 27520 KB Output is correct
2 Correct 14 ms 27520 KB Output is correct
3 Correct 6 ms 27520 KB Output is correct
4 Correct 172 ms 27520 KB Output is correct
5 Correct 11 ms 27520 KB Output is correct
6 Correct 0 ms 27520 KB Output is correct
7 Correct 0 ms 27520 KB Output is correct
8 Correct 0 ms 27520 KB Output is correct
9 Correct 0 ms 27520 KB Output is correct
10 Correct 0 ms 27520 KB Output is correct
11 Correct 8 ms 27520 KB Output is correct
12 Correct 0 ms 27520 KB Output is correct
13 Correct 4 ms 27520 KB Output is correct
14 Correct 17 ms 27520 KB Output is correct
15 Correct 17 ms 27520 KB Output is correct
16 Correct 147 ms 27520 KB Output is correct
17 Correct 0 ms 27520 KB Output is correct
18 Correct 54 ms 27520 KB Output is correct
19 Correct 19 ms 27520 KB Output is correct
20 Correct 0 ms 27520 KB Output is correct