Submission #1605056

---

Source Code Expand

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int W, H, N;
vector<int> X, Y;
map<tuple<int, int, int, int>, long long> dp;

long long solve(int x1, int y1, int x2, int y2){
    if(dp.count(make_tuple(x1, y1, x2, y2))) return dp[make_tuple(x1, y1, x2, y2)];
    if(x1 == x2 || y1 == y2) return 0;

    long long ret = 0;
    for(int i=0; i<N; i++){
        if(X[i] < x1 || X[i] >= x2 || Y[i] < y1 || Y[i] >= y2) continue;
        long long tmp = (x2-x1) + (y2-y1) - 1;
        tmp += solve(x1, y1, X[i], Y[i]);
        tmp += solve(X[i]+1, y1, x2, Y[i]);
        tmp += solve(x1, Y[i]+1, X[i], y2);
        tmp += solve(X[i]+1, Y[i]+1, x2, y2);
        ret = max(ret, tmp);
    }
    dp[make_tuple(x1, y1, x2, y2)] = ret;
    return ret;
}

int main(){
    cin >> W >> H >> N;
    X.resize(N); Y.resize(N);
    for(int i=0; i<N; i++){
        cin >> X[i] >> Y[i];
        X[i]--; Y[i]--;
    }
    cout << solve(0, 0, W, H) << endl;
    return 0;
}

Submission Info

Judge Result