Submission #1677682

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<map>
#include<cmath>
#include<tuple>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int a = 0;a < i;a++){for(int b = 0;b < j;b++)cerr << v[a][b] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int n;
vector<int> y,x;

map<tuple<int,int,int,int> ,int> memo;

ll solve(int y1,int y2,int x1,int x2)
{
	if(memo.find(make_tuple(y2,y2,x1,x2)) != memo.end())
		return memo[make_tuple(y1,y2,x1,x2)];
	
	
	ll ret = 0;
	
	REP(i,n)
	{
		if(y[i] < y1 || y[i] > y2 || x[i] < x1 || x[i] > x2)
			continue;
		
		ll tmp = y2 - y1 + x2 - x1 + 1;
		tmp += solve(y1,y[i] - 1,x1,x[i] - 1);
		tmp += solve(y[i] + 1,y2,x[i] + 1,x2);
		tmp += solve(y1,y[i] - 1,x[i] + 1,x2);
		tmp += solve(y[i] + 1,y2,x1,x[i] - 1);
		
		ret = max(ret,tmp);
		
	}
	
	return memo[make_tuple(y1,y2,x1,x2)] = ret;
}

int main()
{
	int w,h;
	cin >> w >> h >> n;
	x.resize(n);
	y.resize(n);
	REP(i,n)
	{
		cin >> x[i] >> y[i];
	}
	
	cout << solve(1,h,1,w) << endl;
	
	return 0;
}

Submission Info

Judge Result