Submission #1224399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224399		maya_s	Raisins (IOI09_raisins)	C++20	100 / 100	257 ms	68592 KiB

raisins

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;

ll dp[51][51][51][51], sum[51][51][51][51];
ll v[51][51];

int main(){
    ll n, m; cin >> n >> m;
    for(ll i = 0; i < n; i++) for(ll j = 0; j < m; j++) cin >> v[i][j], sum[i][j][i][j] = v[i][j];
    for(ll h = 0; h < n; h++){
        for(ll w = 0; w < m; w++){
            for(ll d = 0; d < n; d++){
                for(ll l = 0; l < m; l++){
                    ll u = d + h, r = l + w;
                    if(u >= n || r >= m) continue;
                    if(u == d && r == l) continue;
                    dp[d][l][u][r] = inf;
                    sum[d][l][u][r] = (d != u ? sum[d][l][d][r] + sum[d+1][l][u][r] : sum[d][l][u][l] + sum[d][l+1][u][r]);
                    for(ll i = d; i < u; i++) dp[d][l][u][r] = min(dp[d][l][u][r], dp[d][l][i][r] + dp[i+1][l][u][r]);
                    for(ll i = l; i < r; i++) dp[d][l][u][r] = min(dp[d][l][u][r], dp[d][l][u][i] + dp[d][i+1][u][r]);
                    dp[d][l][u][r] += sum[d][l][u][r];
                    // cout << d << " " << l << " " << u << " " << r << " " << sum[d][l][u][r] << " " << dp[d][l][u][r] << "\n";
                }
            }
        }
    }
    cout << dp[0][0][n-1][m-1];
}

• Subtask 1: 100 / 100