Submission #1259744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259744		islam_2010	Raisins (IOI09_raisins)	C++20	100 / 100	166 ms	22720 KiB

raisins

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

const int sz = 55;
const int inf = 1e9 + 7;

int a[sz][sz];
int dp[sz][sz][sz][sz];

int main() {
    int n, m;
    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 i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            dp[i][j][i][j] = 0;
            
    for(int ii = 0; ii < n; ii++) {
        for(int jj = 0; jj < m; jj++) {
            for(int i = 0; i + ii < n; i++) {
                for(int j = 0; j + jj < m; j++) {
                    int i2 = i + ii, j2 = j + jj;
                    
                    if(i == i2 && j == j2) continue;
                    int sum = a[i2+1][j2+1] - a[i][j2+1] - a[i2+1][j] + a[i][j];
                    dp[i][j][i2][j2] = inf;
                    for(int k = i; k < i2; k++) {
                        dp[i][j][i2][j2] = min(dp[i][j][i2][j2], dp[i][j][k][j2] + dp[k+1][j][i2][j2] + sum);
                    }
                    for(int k = j; k < j2; k++) {
                         dp[i][j][i2][j2] = min(dp[i][j][i2][j2], dp[i][j][i2][k] + dp[i][k+1][i2][j2] + sum);
                    }
                }
            }
        }
    }

    cout << dp[0][0][n-1][m-1] << endl;
    return 0;
}

• Subtask 1: 100 / 100