Submission #855153

#	Time	Username	Problem	Language	Result	Execution time	Memory
855153		abcvuitunggio	Raisins (IOI09_raisins)	C++17	100 / 100	259 ms	21136 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
int n,m,dp[51][51][51][51],r[51][51];
int f(int i, int j, int k, int l){
    if (i==k&&j==l)
        return 0;
    if (dp[i][j][k][l])
        return dp[i][j][k][l];
    dp[i][j][k][l]=1e9;
    for (int m=i;m<k;m++)
        dp[i][j][k][l]=min(dp[i][j][k][l],f(i,j,m,l)+f(m+1,j,k,l));
    for (int m=j;m<l;m++)
        dp[i][j][k][l]=min(dp[i][j][k][l],f(i,j,k,m)+f(i,m+1,k,l));
    dp[i][j][k][l]+=r[k][l]-r[i-1][l]-r[k][j-1]+r[i-1][j-1];
    return dp[i][j][k][l];
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            cin >> r[i][j];
            r[i][j]+=r[i][j-1]+r[i-1][j]-r[i-1][j-1];
        }
    cout << f(1,1,n,m);
}

• Subtask 1: 100 / 100