B4005求条
  • 板块灌水区
  • 楼主untitled_cpp
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/9/14 21:54
  • 上次更新2024/9/15 09:56:20
查看原帖
B4005求条
1238374
untitled_cpp楼主2024/9/14 21:54

条破防了,求从原来代码上改,用的前缀和优化,到了 O(n4)O(n^4),但只有 75 分……

代码

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int a[15][15];
int sum[15][15];
int n,m;
int ans=-1;
bool check(int x,int y,int x_,int y_){
	int cnt=sum[x_][y_]-sum[x-1][y_]-sum[x_][y-1]+sum[x-1][y-1];
	if(cnt==(x_-x+1)*(y_-y+1)/2) return 1;
	else return 0;
}
int 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++){
			char x;
			cin>>x;
			a[i][j]=x-'0';
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	}
	for(int x=1;x<=n;x++){
		for(int y=1;y<=m;y++){
			for(int x_=x;x_<=n;x_++){
				for(int y_=y;y_<=m;y_++){
					if(check(x,y,x_,y_)) ans=max(ans,(x_-x+1)*(y_-y+1));
				}
			}
		}
	}
	if(ans==-1) cout<<0<<endl;
	else cout<<ans<<endl;
	return 0;
}

2024/9/14 21:54
加载中...