玄关6个 90分谁爱调谁调
  • 板块P1565 牛宫
  • 楼主Zq_water
  • 当前回复4
  • 已保存回复5
  • 发布时间2024/9/12 13:16
  • 上次更新2024/9/12 13:22:37
查看原帖
玄关6个 90分谁爱调谁调
895435
Zq_water楼主2024/9/12 13:16
#include<bits/stdc++.h>
#define INF 2e18
#define endl '\n'
#define PI acos(-1)
#define pb push_back
#define fi first
#define se second
#define int long long
#define mem(x,v) memset(x,v,sizeof x)
using namespace std;
const int N = 205;

int n,m,ans;
int a[N][N],b[N];

bool check(int len){
	for(int i=1;i<=m;i++)b[i]+=b[i-1];
	for(int l=1;l+len-1<=m;l++){
		int r=l+len-1;
		if(b[r]-b[l-1]>0){
			for(int i=m;i>=1;i--)b[i]-=b[i-1];
			return 1;
		}
	}
	for(int i=m;i>=1;i--)b[i]-=b[i-1];
	return 0;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
	for(int l=1;l<=n;l++){
		for(int i=1;i<=m;i++)b[i]=0;
		for(int r=l;r<=n;r++){
			for(int i=1;i<=m;i++)b[i]+=a[r][i];
			int L=1,R=m,mxlen=0;
			while(L<=R){
				int mid=L+R>>1;
				if(check(mid))L=mid+1,mxlen=mid;
				else R=mid-1;
			}
			ans=max(ans,(r-l+1)*mxlen);
		}
	}
	cout<<ans;
	return 0;
}
2024/9/12 13:16
加载中...