oj.uz

Submission #1034943

# Submission time Handle Problem Language Result Execution time Memory
1034943 2024-07-25T22:52:04 Z ArthuroWich Raisins (IOI09_raisins) C++17
100 / 100
 135 ms 59740 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int n, m, r[55][55], pref[55][55], dp[55][55][55][55];
void find(int i1, int j1, int i2, int j2) {
    if (dp[i1][j1][i2][j2] != -1) {
        return;
    }
    dp[i1][j1][i2][j2] = INT_MAX;
    int v = pref[i2][j2]-pref[i1-1][j2]-pref[i2][j1-1]+pref[i1-1][j1-1];
    for (int i = i1; i < i2; i++) {
        find(i1, j1, i, j2);
        find(i+1, j1, i2, j2);
        dp[i1][j1][i2][j2] = min(dp[i1][j1][i2][j2], dp[i1][j1][i][j2]+dp[i+1][j1][i2][j2]+v);
    }
    for (int j = j1; j < j2; j++) {
        find(i1, j1, i2, j);
        find(i1, j+1, i2, j2);
        dp[i1][j1][i2][j2] = min(dp[i1][j1][i2][j2], dp[i1][j1][i2][j]+dp[i1][j+1][i2][j2]+v);
    }
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int x = 1; x <= m; x++) {
                for (int y = 1; y <= m; y++) {
                    dp[i][x][j][y] = -1;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> r[i][j];
            dp[i][j][i][j] = 0;
        }
    }   
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            pref[i][j] = pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+r[i][j];
        }
    }
    find(1, 1, n, m);
    cout << dp[1][1][n][m] << endl;
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 1368 KB Output is correct
7 Correct 0 ms 1628 KB Output is correct
8 Correct 3 ms 5212 KB Output is correct
9 Correct 5 ms 7772 KB Output is correct
10 Correct 7 ms 9564 KB Output is correct
11 Correct 6 ms 7724 KB Output is correct
12 Correct 20 ms 18012 KB Output is correct
13 Correct 29 ms 23644 KB Output is correct
14 Correct 9 ms 9560 KB Output is correct
15 Correct 36 ms 26904 KB Output is correct
16 Correct 6 ms 9308 KB Output is correct
17 Correct 18 ms 19836 KB Output is correct
18 Correct 81 ms 46172 KB Output is correct
19 Correct 118 ms 56244 KB Output is correct
20 Correct 135 ms 59740 KB Output is correct