Submission #530858

#	Time	Username	Problem	Language	Result	Execution time	Memory
530858		Sharky	Raisins (IOI09_raisins)	C++17	100 / 100	201 ms	53300 KiB

raisins

#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 / 100