Submission #426537

#	Time	Username	Problem	Language	Result	Execution time	Memory
426537		haxorman	Raisins (IOI09_raisins)	C++14	100 / 100	522 ms	57664 KiB

raisins

#include <bits/stdc++.h>
using namespace std;

const int mxN = 52;
const long long INF = 1e18 + 7LL;

int n, m;
long long grid[mxN][mxN], pref[mxN][mxN], dp[mxN][mxN][mxN][mxN];

long long rec(int row_1, int col_1, int row_2, int col_2) {
    if (row_1 == row_2 && col_1 == col_2) {
        return 0;
    }

    if (dp[row_1][col_1][row_2][col_2] != -1) {
        return dp[row_1][col_1][row_2][col_2];
    }

    long long ret = INF;
    for (int j = col_1; j < col_2; ++j) {
        ret = min(ret, rec(row_1, col_1, row_2, j) +
                       rec(row_1, j + 1, row_2, col_2));
    }

    for (int i = row_1; i < row_2; ++i) {
        ret = min(ret, rec(row_1, col_1, i, col_2) +
                       rec(i + 1, col_1, row_2, col_2));
    }

    dp[row_1][col_1][row_2][col_2] = ret +
    pref[row_2][col_2] - pref[row_1 - 1][col_2] - pref[row_2][col_1 - 1] + pref[row_1 - 1][col_1 - 1];

    return dp[row_1][col_1][row_2][col_2];
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    memset(dp, -1, sizeof(dp));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> grid[i][j];
        }
    }

    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] + grid[i][j];
        }
    }

    cout << rec(1, 1, n, m) << "\n";
}

• Subtask 1: 100 / 100