Submission #656849

#	Time	Username	Problem	Language	Result	Execution time	Memory
656849		happypotato	Raisins (IOI09_raisins)	C++17	100 / 100	648 ms	51424 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll int MAX = 1e18;
ll int dp[51][51][51][51];
ll int a[51][51], ps[51][51];
int n, m;
void input() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
}
void init() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 1; k <= n; k++) {
                for (int l = 1; l <= m; l++) {
                    dp[i][j][k][l] = -1;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ps[i][j] = (ps[i][j - 1] + ps[i - 1][j] - ps[i - 1][j - 1]) + a[i][j];
        }
    }
}
ll int recur(int x1, int y1, int x2, int y2) {
    if (dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];
    if (x1 == x2 && y1 == y2) return dp[x1][y1][x2][y2] = 0;
    dp[x1][y1][x2][y2] = MAX;
    for (int x = x1; x < x2; x++) {
        ll int cur = recur(x1, y1, x, y2) + recur(x + 1, y1, x2, y2);
        dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], cur);
    }
    for (int y = y1; y < y2; y++) {
        ll int cur = recur(x1, y1, x2, y) + recur(x1, y + 1, x2, y2);
        dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], cur);
    }
    dp[x1][y1][x2][y2] += ps[x2][y2] - ps[x1 - 1][y2] - ps[x2][y1 - 1] + ps[x1 - 1][y1 - 1];
    return dp[x1][y1][x2][y2];
}
int main() {
    input();
    init();
    cout << recur(1, 1, n, m) << endl;
}

• Subtask 1: 100 / 100