首页 > 代码库 > Vijos 1055 奶牛浴场

Vijos 1055 奶牛浴场

Description

求一个不覆盖指定点的最大子矩阵,\(n,m \leqslant 3\times 10^5,S \leqslant 5\times 10^3\) .

Sol

没有名字的算法都叫xjblg算法?

枚举每个点成为极大子矩阵边界的情况,然后维护上下边界.

还有一种情况就是左右边界是矩阵两边的情况,需要预处理一下.

时间复杂度 \(O(S^2)\) 空间复杂度 \(O(S)\)

Code

#include<cstdio>#include<utility>#include<algorithm>#include<functional>#include<iostream>using namespace std;#define mpr make_pairtypedef pair< int,int > pr;typedef long long LL;const int N = 5005;int n,m,k;LL ans;pr g[N];int x[N],y[N];inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘ || ch<‘0‘) ch=getchar();	while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; }int main(){	n=in(),m=in(),k=in();	for(int i=1,u,v;i<=k;i++) u=in(),v=in(),g[i]=mpr(u,v),y[i]=v;	g[++k]=mpr(0,0),y[k]=0,g[++k]=mpr(0,m),y[k]=m,g[++k]=mpr(n,0),y[k]=0,g[++k]=mpr(n,m),y[k]=m;	sort(y+1,y+k+1);	for(int l=1,r;l<=k;l=r+1){		r=l;		while(r<k && y[l]==y[r+1]) ++r;		ans=max(ans,(LL)m*(y[l]-y[l-1]));	}	sort(g+1,g+k+1,less<pr>());	for(int i=1;i<=k;i++){		int u=0,d=n;		for(int j=i+1;j<=k;j++){			ans=max(ans,(LL)(g[j].first-g[i].first)*(d-u));			if(g[j].second>g[i].second) d=min(d,g[j].second);			else if(g[j].second<g[i].second) u=max(u,g[j].second);			else break;		}	}	sort(g+1,g+k+1,greater<pr>());	for(int i=1;i<=k;i++){		int u=0,d=n;		for(int j=i+1;j<=k;j++){			ans=max(ans,(LL)(g[i].first-g[j].first)*(d-u));			if(g[j].second>g[i].second) d=min(d,g[j].second);			else if(g[j].second<g[i].second) u=max(u,g[j].second);			else break;		}	}cout<<ans<<endl;	return 0;}

  

Vijos 1055 奶牛浴场