oj.uz

Submission #530858

# Submission time Handle Problem Language Result Execution time Memory
530858 2022-02-27T02:17:37 Z Sharky Raisins (IOI09_raisins) C++17
100 / 100
 201 ms 53300 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 51
int dp[N][N][N][N], a[N][N], ps[N][N];
int query(int x1, int y1, int x2, int y2) {
    return (ps[x2][y2] + ps[x1 - 1][y1 - 1] - ps[x1 - 1][y2] - ps[x2][y1 - 1]);
}
int solve(int a, int b, int c, int d) {
    if (dp[a][b][c][d] != -1) return dp[a][b][c][d];
    int mn = 1e18;
    for (int i = a + 1; i <= c; i++) {
        mn = min(mn, solve(a, b, i - 1, d) + solve(i, b, c, d));
    }
    for (int i = b + 1; i <= d; i++) {
        mn = min(mn, solve(a, b, c, i - 1) + solve(a, i, c, d));
    }
    dp[a][b][c][d] = (mn + query(a, b, c, d)); 
    return dp[a][b][c][d];
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) for (int l = 0; l < N; l++) dp[i][j][k][l] = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            dp[i][j][i][j] = 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) {
                ps[i][j] = a[i][j];
            } else {
                ps[i][j] = a[i][j] + ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
            }
        }
    }
    cout << solve(1, 1, n, m) << "\n";
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 53196 KB Output is correct
2 Correct 21 ms 53256 KB Output is correct
3 Correct 22 ms 53276 KB Output is correct
4 Correct 21 ms 53196 KB Output is correct
5 Correct 22 ms 53248 KB Output is correct
6 Correct 23 ms 53280 KB Output is correct
7 Correct 28 ms 53164 KB Output is correct
8 Correct 25 ms 53252 KB Output is correct
9 Correct 27 ms 53196 KB Output is correct
10 Correct 26 ms 53240 KB Output is correct
11 Correct 25 ms 53296 KB Output is correct
12 Correct 33 ms 53184 KB Output is correct
13 Correct 43 ms 53292 KB Output is correct
14 Correct 29 ms 53296 KB Output is correct
15 Correct 52 ms 53268 KB Output is correct
16 Correct 22 ms 53196 KB Output is correct
17 Correct 33 ms 53196 KB Output is correct
18 Correct 102 ms 53196 KB Output is correct
19 Correct 167 ms 53296 KB Output is correct
20 Correct 201 ms 53300 KB Output is correct