Submission #2180926

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string.h>
#include <cmath>

using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);++(i))

int w;
int h;

int n;

int x[33];
int y[33];

vector<i64> Xs,Ys;

i64 dp[33][33][33][33];

i64 rec(int x1,int y1,int x2,int y2)
{
	if(x1 < 0 || x2 < 0 || y1 < 0 || y2 < 0) return 0;
	if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];

	i64 result = 0;
	rep(i,1,n)
	{
		if(x1 < x[i] && x[i] < x2 && y1 < y[i] && y[i] < y2)
		{
			i64 now = 0;
			now += Xs[x2] - Xs[x1] - 1;
			now += Ys[y2] - Ys[y1] - 1;

			now += -1;

			now += rec(x1,y1,x[i],y[i]);
			now += rec(x1,y[i],x[i],y2);
			now += rec(x[i],y1,x2,y[i]);
			now += rec(x[i],y[i],x2,y2);

			result = max(result ,now);
		}
	}

	return dp[x1][y1][x2][y2] = result;
}

#define INIT(i) rep(i,0,32)

int main()
{
	INIT(i) INIT(j) INIT(k) INIT(l) dp[i][j][k][l] = -1;
	cin>> w >> h >> n;
	rep(i,1,n)
	{
		cin >> x[i] >> y[i];
		Xs.push_back(x[i]);
		Ys.push_back(y[i]);
	}

	Xs.push_back(0);
	Ys.push_back(0);
	Xs.push_back(w + 1);
	Ys.push_back(h + 1);

	sort(Xs.begin(),Xs.end());
	sort(Ys.begin(),Ys.end());
	Xs.erase(unique(Xs.begin(),Xs.end()),Xs.end());
	Ys.erase(unique(Ys.begin(),Ys.end()),Ys.end());

	int w = Xs.size() - 1;
	int h = Ys.size() - 1;
	rep(i,1,n)
	{
		x[i] = lower_bound(Xs.begin(),Xs.end(),x[i]) - Xs.begin();
		y[i] = lower_bound(Ys.begin(),Ys.end(),y[i]) - Ys.begin();
	}

	cout << rec(0,0,w,h) << endl;

}

Submission Info

Judge Result