Submission #1218748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218748		tapilyoca	Raisins (IOI09_raisins)	C++20	100 / 100	659 ms	53444 KiB

raisins

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const ll INF = 1e18;
 
ll N, M;
ll memo[51][51][51][51];
vector<vector<ll> > grid;
vector<vector<ll> > pfxSum;
 
ll dp(ll top, ll bottom, ll left, ll right) {
 
    assert(top <= bottom && left <= right);
 
    if (top == bottom && left == right) return 0;
    if (memo[top][bottom][left][right] != -1) {
        return memo[top][bottom][left][right];
    }
 
    ll currCost = pfxSum[bottom][right] - pfxSum[top - 1][right] - pfxSum[bottom][left - 1] + pfxSum[top - 1][left - 1];
    
    ll minForHori = INF, minForVert = INF;
    if (left != right) {
        for (ll endLeft = left; endLeft < right; endLeft++) {
            minForHori = min(minForHori, dp(top, bottom, left, endLeft) + dp(top, bottom, endLeft + 1, right));
        }
    }
    if (top != bottom) {
        for (ll endTop = top; endTop < bottom; endTop++) {
            minForVert = min(minForVert, dp(top, endTop, left, right) + dp(endTop + 1, bottom, left, right));
        }
    }
 
    return memo[top][bottom][left][right] = currCost + min(minForHori, minForVert);
 
}
 
int main() {
 
    cin.tie(0);
    ios_base::sync_with_stdio(false);
 
    memset(memo, -1LL, sizeof(memo));
 
    cin >> N >> M;
    grid.resize(N + 1, vector<ll>(M + 1, 0));
    for (ll i = 1; i <= N; i++) {
        for (ll j = 1; j <= M; j++) {
            cin >> grid[i][j];
        }
    }
 
    pfxSum.resize(N + 1, vector<ll>(M + 1, 0));
    for (ll i = 1; i <= N; i++) {
        for (ll j = 1; j <= M; j++) {
            pfxSum[i][j] = pfxSum[i - 1][j] + pfxSum[i][j - 1] - pfxSum[i - 1][j - 1] + grid[i][j];
        }
    }
    
    cout << dp(1, N, 1, M) << endl;
 
}

• Subtask 1: 100 / 100