IOI '04 P4 - Phidias

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int W, H; cin >> W >> H;
    vector<vector<int>> minWasted(1+W, vector<int>(1+H));
    for (int w = 0; w <= W; ++w) {
        for (int h = 0; h <= H; ++h) minWasted[w][h] = w*h;
    }

    int N; cin >> N;
    while (N--) {
        int w, h; cin >> w >> h;
        minWasted[w][h] = 0;
    }

    for (int w = 1; w <= W; ++w) {
        for (int h = 1; h <= H; ++h) {
            for (int w1 = 1; w1 < w; ++w1) { // vertical cut
                minWasted[w][h] = min(minWasted[w][h], minWasted[w1][h] + minWasted[w-w1][h]);
            }
            for (int h1 = 1; h1 < h; ++h1) { // horizontal cut
                minWasted[w][h] = min(minWasted[w][h], minWasted[w][h1] + minWasted[w][h-h1]);
            }
        }
    }
    cout << minWasted[W][H] << endl;
    return 0;
}