Raisins

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 52;
const int INF = 1000000007;

int n, m;
int a[MAXN][MAXN], p[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];

inline int get (int x1, int y1, int x2, int y2) {
    return p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] + p[x1-1][y1-1];
}

int f (int x1, int y1, int x2, int y2) {
    if (dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];
    if (x1 == x2 && y1 == y2) return 0;
    int res = INF;
    int sum = get(x1, y1, x2, y2);
    for (int i = x1; i < x2; i++) {
        res = min(res, sum + f(x1, y1, i, y2) + f(i+1, y1, x2, y2));
    }
    for (int i = y1; i < y2; i++) {
        res = min(res, sum + f(x1, y1, x2, i) + f(x1, i+1, x2, y2));
    }
    dp[x1][y1][x2][y2] = res;
    return res;
}

int main () {
    memset(dp, -1, sizeof dp);
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            cin >> a[i][j];
            p[i][j] = a[i][j] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
        }
    }
    cout << f(1, 1, n, m);
    return 0;
}