Submission #1299343

#TimeUsernameProblemLanguageResultExecution timeMemory
1299343coolboy19521Bomb (IZhO17_bomb)C++20
38 / 100
204 ms56136 KiB
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"

#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;i>=(a);i--)
#define R0F(i,a)ROF(i,0,a)
#define REP(a)F0R(_,a)

using namespace std;

const int mxn = 2501;

string a[mxn];
int dp[2][mxn][mxn];
int w[mxn];
int att[mxn];

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m; cin >> n >> m;
	F0R(i,n)cin>>a[i];
	int mw = INT_MAX;
	F0R(j,m){
		F0R(i,n)if(a[i][j]=='1'){
			dp[0][i][j]=1;
			if(i)dp[0][i][j] += dp[0][i-1][j];
		}
		R0F(i,n)if(a[i][j]=='1'){
			dp[1][i][j]=1;
			if(i<n-1)dp[1][i][j] += dp[1][i+1][j];
		}
		F0R(i,n){
			if(a[i][j]=='1')att[i]++;
			else {
				if(att[i])mw=min(mw,att[i]);
				att[i]=0;
			}
		}
	}
	F0R(j,m)if(att[j])mw=min(mw,att[j]);
	int mh=INT_MAX;
	F0R(i,n)F0R(j,m)if(a[i][j]=='1')mh=min(mh,dp[0][i][j]+dp[1][i][j]-1);
	/*F0R(i,n){
		F0R(j,m)cout<<dp[1][i][j]<<' ';cout<<endl;
	}
	cout << mw << ' ' << mh << endl;*/
	fill_n(w,mw+1,mh);
	F0R(i,n){
		int ln=0,ma=INT_MAX,mb=INT_MAX;
		F0R(j,m){
			if (a[i][j]=='1'){
				ln++,ma=min(ma,dp[0][i][j]),mb=min(mb,dp[1][i][j]);
				w[ln]=min(w[ln],ma+mb-1);
			}else ln=0;
		}
	}
	int ans=0;
	F0R(i,mw+1)ans=max(ans,i*w[i]);
	cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...