IOI '09 P4 - Raisins

#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> a(1+n, vector<int>(1+m));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) cin >> a[i][j];
    }
    vector<vector<int>> pre = a;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) pre[i][j] += pre[i][j-1];
        for (int j = 1; j <= m; ++j) pre[i][j] += pre[i-1][j];
    }
    auto rangeSum = [&](int top, int bottom, int left, int right) {
        --top, --left;
        return pre[bottom][right] - pre[bottom][left] - pre[top][right] + pre[top][left];
    };

    // dp with O((nm)^2) states, and O(n+m) transitions for each state
    vector<vector<vector<vector<int>>>> minCost(1+n, vector<vector<vector<int>>>(1+n, vector<vector<int>>(1+m, vector<int>(1+m, INF))));
    // in order of increasing size
    for (int height = 1; height <= n; ++height) {
        for (int width = 1; width <= m; ++width) {
            for (int top = 1, bottom = height; bottom <= n; ++top, ++bottom) {
                for (int left = 1, right = width; right <= m; ++left, ++right) {
                    // find minCost[top][bottom][left][right]
                    int cutCost = rangeSum(top, bottom, left, right);
                    int &cur = minCost[top][bottom][left][right];
                    if (height == 1 && width == 1) {
                        cur = 0;
                        continue;
                    }

                    // try a horizontal cut
                    for (int middle = top+1; middle <= bottom; ++middle) {
                        int x = minCost[top][middle-1][left][right];
                        int y = minCost[middle][bottom][left][right];
                        cur = min(cur, cutCost + x + y);
                    }

                    // try a vertical cut
                    for (int middle = left+1; middle <= right; ++middle) {
                        int x = minCost[top][bottom][left][middle-1];
                        int y = minCost[top][bottom][middle][right];
                        cur = min(cur, cutCost + x + y);
                    }
                }
            }
        }
    }
    cout << minCost[1][n][1][m] << endl;
    return 0;
}