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...