Advertisement
Guest User

Untitled

a guest
Jun 6th, 2015
442
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.40 KB | None | 0 0
  1. //...
  2. #include<iostream>
  3. #include<stdio.h>
  4. #include<math.h>
  5. #include<iomanip>
  6. #include<algorithm>
  7. #include<vector>
  8. #include<map>
  9. #include<queue>
  10. #include<string>
  11. #define Pi 3.14159265358
  12. #define mod9 %1000000009
  13. #define mod7 %1000000007
  14. #define INF 1000000000
  15. #define LL  long long
  16. using namespace std;
  17.  int n,m,k,i,j,x,y,xa,ya,xb,yb;
  18.  LL ans;
  19.  bool a[6002][6004];
  20.  LL d[6002],h[6002];
  21.  vector<pair<int,int> > p;
  22. int main(){
  23.     scanf("%d%d%d",&m,&n,&k);
  24.     for (i=1;i<=m;i++)
  25.         for (j=1;j<=n;j++)
  26.             a[i][j]=1;
  27.     for (i=1;i<=k;i++){
  28.         scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
  29.         if (xa>xb) swap(xa,xb);
  30.         if (ya>yb)swap(ya,yb);
  31.         xa++;ya++;
  32.         for (x=xa-1;x<=xb+1;x++)
  33.             for (y=ya-1;y<=yb+1;y++){
  34.                 a[x][y]=0;
  35.             }
  36.         ans=max(ans,(xb-xa+1)*1ll*(yb-ya+1));
  37.     }
  38.  
  39.     for (i=1;i<=m;i++){
  40.         p.clear();
  41.         for (j=1;j<=n;j++){
  42.             if (a[i][j]==0) h[j]=0; else h[j]=h[j]+1;
  43.             while (p.size() && p[p.size()-1].first>=h[j]) p.pop_back();
  44.             if (p.size()==0) d[j]=h[j]*j;
  45.             else {
  46.                 x=p[p.size()-1].second;
  47.                 y=p[p.size()-1].first;
  48.                 d[j]=max(h[j]*(j-x),d[x]+y*(j-x));
  49.             }
  50.             ans=max(ans,max(d[j],h[j]));
  51.             p.push_back(make_pair(h[j],j));
  52.         };
  53.     }
  54.     cout<<ans<<endl;
  55.  return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement