oj.uz

Submission #1112792

# Submission time Handle Problem Language Result Execution time Memory
1112792 2024-11-14T20:50:57 Z karok Raisins (IOI09_raisins) C++17
100 / 100
 899 ms 72076 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXN = 55;

ll dp[MAXN][MAXN][MAXN][MAXN];
int a[MAXN][MAXN];

ll rec(int ar, int ac, int br, int bc) {
    if(ar > br || ac > bc) return 0;
    if(ar == br && ac == bc) return 0;
    if(dp[ar][ac][br][bc] != -1) return dp[ar][ac][br][bc];

    ll res = LLONG_MAX;
    for(int i = ar;i < br;i++) { // row cut
        res = min(res, rec(ar, ac, i, bc) + rec(i + 1, ac, br, bc));
    }
    for(int i = ac; i < bc;i++) {
        res = min(res, rec(ar, ac, br, i) + rec(ar, i + 1, br, bc));

    }

    for(int i =ar;i <= br;i++) {
        for(int j = ac; j <= bc;j++) {
            res += a[i][j];
        }
    }
    return dp[ar][ac][br][bc] = res;
}

int main() {
    memset(dp, -1, sizeof(dp));
    int n, m;
    cin >> n >> m;
    for(int i =0;i < n;i++) {
        for(int j =0; j < m;j++) {
            cin >> a[i][j];
        }
    }
    cout << rec(0, 0, n - 1, m -1) << '\n';
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 72016 KB Output is correct
2 Correct 21 ms 72016 KB Output is correct
3 Correct 38 ms 71872 KB Output is correct
4 Correct 38 ms 71928 KB Output is correct
5 Correct 27 ms 72008 KB Output is correct
6 Correct 26 ms 72016 KB Output is correct
7 Correct 28 ms 72012 KB Output is correct
8 Correct 34 ms 72076 KB Output is correct
9 Correct 40 ms 72032 KB Output is correct
10 Correct 46 ms 72016 KB Output is correct
11 Correct 55 ms 71916 KB Output is correct
12 Correct 93 ms 72008 KB Output is correct
13 Correct 194 ms 71952 KB Output is correct
14 Correct 80 ms 72016 KB Output is correct
15 Correct 208 ms 72072 KB Output is correct
16 Correct 48 ms 71984 KB Output is correct
17 Correct 118 ms 72056 KB Output is correct
18 Correct 465 ms 72072 KB Output is correct
19 Correct 836 ms 72076 KB Output is correct
20 Correct 899 ms 72076 KB Output is correct