Submission #838228

#	Time	Username	Problem	Language	Result	Execution time	Memory
838228		matthewhutama	Raisins (IOI09_raisins)	C++14	100 / 100	233 ms	72016 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll memo[55][55][55][55];
ll n,m,grid[55][55];
ll pref[55][55];
ll sum(ll a, ll b, ll c, ll d){
    return pref[c][d] - pref[c][b - 1] - pref[a - 1][d] + pref[a - 1][b - 1];
}

ll dp (ll a, ll b, ll c, ll d){
    if (memo[a][b][c][d] != -1) return memo[a][b][c][d];
    if (a == c && b == d) return 0;
    ll sv = 1e18;
    for (int i = a; i <= c - 1; i ++){
        sv = min (sv, dp (a, b, i, d) + dp (i + 1, b, c, d) + sum(a, b, c, d));
    }
    for (int i = b; i <= d - 1; i ++){
        sv = min (sv, dp (a, b, c, i) + dp (a, i + 1, c, d) + sum(a, b, c, d));
    }
    memo[a][b][c][d] = sv;
    return memo[a][b][c][d];
}
int main(){
    memset(memo, -1 , sizeof(memo));
    cin >> n >> m;
    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 <<pref[i][j];
        }
    }
    cout << dp(1, 1, n, m);
}

• Subtask 1: 100 / 100