Submission #229091

---

Source Code Expand

#include <cstdio> 
#include <cstdlib> 
#include <cmath> 
#include <cstring> 
#include <climits> 
#include <cfloat> 
#include <map> 
#include <utility> 
#include <set> 
#include <iostream> 
#include <memory> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <functional> 
#include <sstream> 
#include <complex> 
#include <stack> 
#include <queue> 
#include <numeric>
#include <cassert>

#define FOR(i, min, max) for (int i = (min); i < (max); ++i) 
#define FORE(i, min, max) for (int i = (min); i <= (max); ++i) 
#define REP(i, n) for (int i = 0; i < (n); ++i) 
#define REPV(vec, i) for (int i = 0; i < (int)(vec.size()); ++i) 
#define FOR_EACH(vec, it) for (typeof((vec).begin()) it = (vec).begin(); it != (vec).end(); ++it)

using namespace std; 
static const double EPS = 1e-12; 
typedef long long ll; 


ll mem[32][32][32][32];  /* [startx][starty][endx][endy] */
int W, H;
int N;
vector<pair<int, int> > P;
int XtoIdx[1<<20];
int YtoIdx[1<<20];

ll solve(int sx, int sy, int ex, int ey) {
    if (sx > ex || sy > ey) {
        return 0;
    }

    ll &ret = mem[XtoIdx[sx]][YtoIdx[sy]][XtoIdx[ex]][YtoIdx[ey]];
    if (ret < 0) {
        ret = 0;
        int sizex = (ex-sx+1);
        int sizey = (ey-sy+1);
        int numC = (sizex+sizey-1);
        REP(i, N) if (sx <= P[i].first  && P[i].first  <= ex && 
                      sy <= P[i].second && P[i].second <= ey) {
            ll n = numC;
            // left upper
            n += solve(sx, sy, P[i].first-1, P[i].second-1);
            // right upper
            n += solve(P[i].first+1, sy, ex, P[i].second-1);
            // left lower
            n += solve(sx, P[i].second+1, P[i].first-1, ey);
            // right upper
            n += solve(P[i].first+1, P[i].second+1, ex, ey);
            if (n > ret) {
                ret = n;
            }
        }
        //cout << "[DEBUG]: (" << sx << "," << sy << "),(" << ex << "," << ey << "): " << numC << "," << ret << endl;
    }
    return ret;
}

int main(void)
{
    cin >> W >> H;
    cin >> N;

    P.resize(N);
    set<int> X;
    set<int> Y;
    X.insert(1);
    X.insert(W);
    Y.insert(1);
    Y.insert(H);
    REP(i, N) {
        cin >> P[i].first >> P[i].second;
        X.insert(P[i].first+1);
        X.insert(P[i].first-1);
        Y.insert(P[i].second+1);
        Y.insert(P[i].second-1);
    }

    memset(XtoIdx, -1, sizeof(XtoIdx));
    memset(YtoIdx, -1, sizeof(YtoIdx));
    int xidx = 0;
    for (set<int>::iterator it=X.begin(); it!=X.end(); it++) {
        XtoIdx[*it] = xidx++;
    }
    int yidx = 0;
    for (set<int>::iterator it=Y.begin(); it!=Y.end(); it++) {
        YtoIdx[*it] = yidx++;
    }

    memset(mem, -1, sizeof(mem));
    ll ans = solve(1, 1, W, H);

    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result