Submission #2208341

---

Source Code Expand

#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<tuple>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>

#define ll __int64
//#define __int64 long long
int w,h;
int n;
int x[200000],y[200000];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const int M=81;

map<tuple<int,int,int,int>,int>dp;

int dfs(int y1,int x1,int y2,int x2){

	if(y1>y2||x1>x2)return 0;
	if(dp[make_tuple(y1,x1,y2,x2)]>0)return dp[make_tuple(y1,x1,y2,x2)];
		//cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
	int ret=0;

	for(int i=y1;i<=y2;i++){
		for(int j=x1;j<=x2;j++){
			int tmp=0;

			rep(k,n){
				if(i==y[k]&&j==x[k]){

					tmp+=max(0,i-y1);
					tmp+=max(0,j-x1);
					tmp+=max(0,y2-i);
					tmp+=max(0,x2-j);
		
					//cout<<"*"<<i<<" "<<j<<" "<<tmp<<endl;
					tmp+=dfs(i+1,j+1,y2,x2);//右下
					tmp+=dfs(i+1,x1,y2,j-1);//左下
					tmp+=dfs(y1,j+1,i-1,x2);//右上
					tmp+=dfs(y1,x1,i-1,j-1);//左上
					ret=max(ret,tmp);
				}
			}
		}
	}

	return dp[make_tuple(y1,x1,y2,x2)]=ret;
}

int main(){
	cin>>w>>h;
	cin>>n;
	rep(i,n){cin>>x[i]>>y[i];x[i]--;y[i]--;}
	cout<<dfs(0,0,h-1,w-1)+n<<endl;
	return 0;
}

Submission Info

Judge Result