Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //...
- #include<iostream>
- #include<stdio.h>
- #include<math.h>
- #include<iomanip>
- #include<algorithm>
- #include<vector>
- #include<map>
- #include<queue>
- #include<string>
- #define Pi 3.14159265358
- #define mod9 %1000000009
- #define mod7 %1000000007
- #define INF 1000000000
- #define LL long long
- using namespace std;
- int n,m,k,i,j,x,y,xa,ya,xb,yb;
- LL ans;
- bool a[6002][6004];
- LL d[6002],h[6002];
- vector<pair<int,int> > p;
- int main(){
- scanf("%d%d%d",&m,&n,&k);
- for (i=1;i<=m;i++)
- for (j=1;j<=n;j++)
- a[i][j]=1;
- for (i=1;i<=k;i++){
- scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
- if (xa>xb) swap(xa,xb);
- if (ya>yb)swap(ya,yb);
- xa++;ya++;
- for (x=xa-1;x<=xb+1;x++)
- for (y=ya-1;y<=yb+1;y++){
- a[x][y]=0;
- }
- ans=max(ans,(xb-xa+1)*1ll*(yb-ya+1));
- }
- for (i=1;i<=m;i++){
- p.clear();
- for (j=1;j<=n;j++){
- if (a[i][j]==0) h[j]=0; else h[j]=h[j]+1;
- while (p.size() && p[p.size()-1].first>=h[j]) p.pop_back();
- if (p.size()==0) d[j]=h[j]*j;
- else {
- x=p[p.size()-1].second;
- y=p[p.size()-1].first;
- d[j]=max(h[j]*(j-x),d[x]+y*(j-x));
- }
- ans=max(ans,max(d[j],h[j]));
- p.push_back(make_pair(h[j],j));
- };
- }
- cout<<ans<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement