oj.uz

Submission #18057

# Submission time Handle Problem Language Result Execution time Memory
18057 2016-01-19T10:37:20 Z chan492811 L 모양의 종이 자르기 (KOI15_cut) C++
25 / 25
 336 ms 27520 KB 
#include <cstdio>
#include <cstring>
#include <algorithm>
#define n 50
#define INF 1000000000
using namespace std;
int l_paper[51][51][51][51],rec[51][51];
int h1,w1,h2,w2;
int main(){
    int i,j,k,l,p;
    scanf("%d %d %d %d",&h1,&w1,&h2,&w2);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            rec[i][j]=INF;
            if(i==1 || j==1){ rec[i][j]=max(i,j); continue; }
            if(i==j){ rec[i][j]=1; continue; }
            for(k=1;k<i;k++) rec[i][j]=min(rec[i][j],rec[k][j]+rec[i-k][j]);
            for(k=1;k<j;k++) rec[i][j]=min(rec[i][j],rec[i][k]+rec[i][j-k]);
        }
    }
    for(i=1;i<=h1;i++){
        for(j=1;j<=w1;j++){
            for(k=1;k<i;k++){
                for(l=1;l<j;l++){
                    l_paper[i][j][k][l]=INF;
                    l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[k][j-l]+rec[i-k][j]);
                    l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[i-k][l]+rec[i][j-l]);
                    for(p=1;p<j-l;p++) l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[p][i]+l_paper[i][j-p][k][l]);
                    for(p=1;p<l;p++) l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[p][i-k]+l_paper[i][j-p][k][l-p]);
                    for(p=1;p<k;p++) l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[p][j-l]+l_paper[i-p][j][k-p][l]);
                    for(p=1;p<i-k;p++) l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[p][j]+l_paper[i-p][j][k][l]);
                }
            }
        }
    }printf("%d",l_paper[h1][w1][h2][w2]);
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 27520 KB Output is correct
2 Correct 75 ms 27520 KB Output is correct
3 Correct 336 ms 27520 KB Output is correct
4 Correct 261 ms 27520 KB Output is correct
5 Correct 333 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 319 ms 27520 KB Output is correct
12 Correct 0 ms 27520 KB Output is correct
13 Correct 3 ms 27520 KB Output is correct
14 Correct 81 ms 27520 KB Output is correct
15 Correct 36 ms 27520 KB Output is correct
16 Correct 225 ms 27520 KB Output is correct
17 Correct 229 ms 27520 KB Output is correct
18 Correct 104 ms 27520 KB Output is correct
19 Correct 25 ms 27520 KB Output is correct
20 Correct 335 ms 27520 KB Output is correct