oj.uz

Submission #18032

# Submission time Handle Problem Language Result Execution time Memory
18032 2016-01-18T13:20:08 Z gs14004 L 모양의 종이 자르기 (KOI15_cut) C++14
25 / 25
 125 ms 27520 KB 
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
 
int dp[51][51];
int dp2[51][51][51][51];
 
int f(int h1, int w1, int h2, int w2){
    if(w2 == 0 || h2 == 0){
        return dp[h1][w1];
    }
    if(~dp2[h1][w1][h2][w2]) return dp2[h1][w1][h2][w2];
    int ret = 1e9;
    for(int j=1; j<h1; j++){
        if(j <= h2){
            ret = min(ret, dp[w1 - w2][j] + f(h1 - j, w1, h2 - j, w2));
        }
        else{
            ret = min(ret, dp[w1][h1 - j] + f(j, w1, h2, w2));
        }
    }
    for(int j=1; j<w1; j++){
        if(j <= w2){
            ret = min(ret, dp[j][h1 - h2] + f(h1, w1 - j, h2, w2 - j));
        }
        else{
            ret = min(ret, dp[w1 - j][h1] + f(h1, j, h2, w2));
        }
    }
    return dp2[h1][w1][h2][w2] = ret;
}
 
int main(){
    memset(dp2,-1,sizeof(dp2));
    int a, b, c, d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    for(int i=1; i<=50; i++){
        for(int j=1; j<=50; j++){
            if(i == j) dp[i][j] = 1;
            else{
                dp[i][j] = 1e9;
                for(int k=1; k<i; k++){
                    dp[i][j] = min(dp[i][j], dp[k][j] + dp[i-k][j]);
                }
                for(int k=1; k<j; k++){
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j-k]);
                }
            }
        }
    }
    printf("%d",f(a, b, c, d));
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 27520 KB Output is correct
2 Correct 6 ms 27520 KB Output is correct
3 Correct 5 ms 27520 KB Output is correct
4 Correct 122 ms 27520 KB Output is correct
5 Correct 10 ms 27520 KB Output is correct
6 Correct 0 ms 27520 KB Output is correct
7 Correct 3 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 3 ms 27520 KB Output is correct
11 Correct 8 ms 27520 KB Output is correct
12 Correct 4 ms 27520 KB Output is correct
13 Correct 0 ms 27520 KB Output is correct
14 Correct 13 ms 27520 KB Output is correct
15 Correct 8 ms 27520 KB Output is correct
16 Correct 125 ms 27520 KB Output is correct
17 Correct 3 ms 27520 KB Output is correct
18 Correct 37 ms 27520 KB Output is correct
19 Correct 17 ms 27520 KB Output is correct
20 Correct 3 ms 27520 KB Output is correct