oj.uz

Submission #530857

# Submission time Handle Problem Language Result Execution time Memory
530857 2022-02-27T02:12:19 Z Sharky Raisins (IOI09_raisins) C++17
10 / 100
 189 ms 53324 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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 53192 KB Output is correct
2 Correct 22 ms 53276 KB Output is correct
3 Incorrect 21 ms 53172 KB Output isn't correct
4 Incorrect 22 ms 53208 KB Output isn't correct
5 Incorrect 21 ms 53184 KB Output isn't correct
6 Incorrect 22 ms 53264 KB Output isn't correct
7 Incorrect 26 ms 53196 KB Output isn't correct
8 Incorrect 27 ms 53256 KB Output isn't correct
9 Incorrect 26 ms 53252 KB Output isn't correct
10 Incorrect 27 ms 53216 KB Output isn't correct
11 Incorrect 33 ms 53180 KB Output isn't correct
12 Incorrect 34 ms 53224 KB Output isn't correct
13 Incorrect 41 ms 53284 KB Output isn't correct
14 Incorrect 28 ms 53188 KB Output isn't correct
15 Incorrect 58 ms 53316 KB Output isn't correct
16 Incorrect 24 ms 53292 KB Output isn't correct
17 Incorrect 35 ms 53196 KB Output isn't correct
18 Incorrect 105 ms 53304 KB Output isn't correct
19 Incorrect 156 ms 53308 KB Output isn't correct
20 Incorrect 189 ms 53324 KB Output isn't correct