Submission #1210930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210930		Hamed_Ghaffari	Raisins (IOI09_raisins)	C++20	100 / 100	86 ms	21060 KiB

raisins

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

#define mins(a, b) (a = min(a,b))

const int MXN = 51;

int n, m, a[MXN][MXN], dp[MXN][MXN][MXN][MXN];

inline int get(int i, int j, int k, int l) {
    return a[k][l] - a[i-1][l] - a[k][j-1] + a[i-1][j-1];
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) {
            cin >> a[i][j];
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
        }
    for(int lnx=1; lnx<=n; lnx++)
        for(int i=1, k=lnx; k<=n; i++, k++)
            for(int lny=1+(lnx==1); lny<=m; lny++)
                for(int j=1, l=lny; l<=m; j++, l++) {
                    dp[i][j][k][l] = 2e9;
                    for(int x=i; x<k; x++)
                        mins(dp[i][j][k][l], dp[i][j][x][l]+dp[x+1][j][k][l]+get(i,j,k,l));
                    for(int x=j; x<l; x++)
                        mins(dp[i][j][k][l], dp[i][j][k][x]+dp[i][x+1][k][l]+get(i,j,k,l));
                }
    cout << dp[1][1][n][m] << '\n';
    return 0;
}

• Subtask 1: 100 / 100