Submission #2180843

---

Source Code Expand

#include <iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef long long ll;
typedef pair<int,int> pint;
const int inf   = 1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

ll n,dp[70][70][70][70],a[100][100];
pint p[30];

ll rec(int l,int r,int u,int d){
  if(dp[l][r][u][d]!=-1)return dp[l][r][u][d];
  ll ret=0;
  rep(i,n){
    ll tmp=0;
    int x=p[i].first,y=p[i].second;
    if(l<=x&&x<=r&&u<=y&&y<=d){
      REP(j,l,r+1)tmp+=a[j][y];
      REP(j,u,d+1)tmp+=a[x][j];
      tmp-=a[x][y];
      tmp+=rec(l,x-1,u,y-1)+rec(l,x-1,y+1,d)+rec(x+1,r,u,y-1)+rec(x+1,r,y+1,d);
      }
    ret=max(ret,tmp);
    }
  return dp[l][r][u][d]=ret;
  }
  
int main(){
  ll w,h;
  cin>>w>>h;
  cin>>n;
  pint x[n],y[n];  
  rep(i,n){
    int c,d;
    cin>>c>>d;
    x[i]=pint(c,i);
    y[i]=pint(d,i);
    }
  sort(x,x+n);
  sort(y,y+n);
  rep(i,71)rep(j,71)a[i][j]=1;
  a[0][70]=x[0].first-1;
  rep(i,n-1)a[2*i+2][70]=x[i+1].first-x[i].first-1;
  a[2*n][70]=w-x[n-1].first;
  a[70][0]=y[0].first-1;
  rep(i,n-1)a[70][2*i+2]=y[i+1].first-y[i].first-1;
  a[70][2*n]=h-y[n-1].first;
  rep(i,2*n+1)rep(j,2*n+1)a[i][j]=a[70][j]*a[i][70];
  rep(i,n){
    p[x[i].second].first=2*i+1;
    p[y[i].second].second=2*i+1;
    }                   
  rep(i,2*n+1)rep(j,2*n+1)rep(k,2*n+1)rep(l,2*n+1)
    dp[i][j][k][l]=-1;
  cout<<rec(0,2*n,0,2*n)<<endl;
  return 0;
  }

Submission Info

Judge Result