oj.uz

Submission #544663

# Submission time Handle Problem Language Result Execution time Memory
544663 2022-04-02T14:17:42 Z pokmui9909 L 모양의 종이 자르기 (KOI15_cut) C++17
25 / 25
 304 ms 20072 KB 
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
ll D[55][55];
ll D2[55][55][55][55];
 
ll dfs(ll n, ll m)
{
    if(n < m) swap(n, m);
    if(n == m) return 1;
    if(D[n][m]) return D[n][m];
    if(n >= 3 * m) return dfs(n - m, m) + 1;
 
    ll ans = 1e15;
    for(int i = 1; i <= n - 1; i++) ans = min(ans, dfs(i, m) + dfs(n - i, m));
    for(int i = 1; i <= m - 1; i++) ans = min(ans, dfs(n, i) + dfs(n, m - i));
 
    return D[n][m] = ans;
}
 
ll dfs2(ll x1, ll y1, ll x2, ll y2)
{
    if(x2 == 0 || y2 == 0) return dfs(x1, y1);
    if(D2[x1][y1][x2][y2]) return D2[x1][y1][x2][y2];
 
    ll ans = 1e15;
 
    for(int i = 1; i <= y1 - y2 - 1; i++) ans = min(ans, dfs(x1, i) + dfs2(x1, y1 - i, x2, y2));
    for(int i = 1; i <= x1 - x2 - 1; i++) ans = min(ans, dfs(y1, i) + dfs2(x1 - i, y1, x2, y2));
    for(int i = y1 - y2 + 1; i < y1; i++) ans = min(ans, dfs(x1 - x2, y1 - i) + dfs2(x1, i, x2, i - (y1 - y2)));
    for(int i = x1 - x2 + 1; i < x1; i++) ans = min(ans, dfs(y1 - y2, x1 - i) + dfs2(i, y1, i - (x1 - x2), y2));
    ans = min(ans, dfs(x1 - x2, y1) + dfs(y1 - y2, x2));
    ans = min(ans, dfs(x1, y1 - y2) + dfs(x1 - x2, y2));
 
    return D2[x1][y1][x2][y2] = ans;
}
 
int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
 
    ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    cout << dfs2(x1, y1, x2, y2);
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 10256 KB Output is correct
2 Correct 17 ms 6092 KB Output is correct
3 Correct 17 ms 11044 KB Output is correct
4 Correct 304 ms 20072 KB Output is correct
5 Correct 38 ms 11084 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 21 ms 10792 KB Output is correct
12 Correct 4 ms 2760 KB Output is correct
13 Correct 4 ms 2772 KB Output is correct
14 Correct 29 ms 11596 KB Output is correct
15 Correct 25 ms 5252 KB Output is correct
16 Correct 287 ms 19128 KB Output is correct
17 Correct 13 ms 10372 KB Output is correct
18 Correct 76 ms 10276 KB Output is correct
19 Correct 23 ms 6260 KB Output is correct
20 Correct 10 ms 10068 KB Output is correct