제출 #1299250

#제출 시각아이디문제언어결과실행 시간메모리
1299250coolboy19521Bomb (IZhO17_bomb)C++20
25 / 100
1099 ms55748 KiB
#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 = 2500; short dp[4][mxn][mxn]; int main() { cin.tie(nullptr)->sync_with_stdio(false); vector<string> a; int n, m; cin >> n >> m; F0R(i,n){ string s; cin >> s; a.push_back(s); } F0R(i,n){ F0R(j,m){ if (a[i][j]=='1')dp[0][i][j]=dp[1][i][j]=dp[2][i][j]=dp[3][i][j]=1; if (a[i][j]=='1'){ if (i)dp[0][i][j]+=dp[0][i-1][j]; if (j)dp[1][i][j]+=dp[1][i][j-1]; } } R0F(j,m){ if (a[i][j]=='1' and j<m-1)dp[3][i][j]+=dp[3][i][j+1]; } } R0F(i,n){ F0R(j,m){ if (a[i][j]=='1' and i<n-1)dp[2][i][j]+=dp[2][i+1][j]; } } int mh = mxn, mw = mxn; /*F0R(i,n){ F0R(j,n)cout<<dp[1][i][j]<<' ';cout<<endl; }*/ F0R(i,n)F0R(j,m)if(a[i][j]=='1') mh = min(mh, dp[0][i][j]+dp[2][i][j]-1), mw=min(mw,dp[1][i][j]+dp[3][i][j]-1); //cout << "mw: " << mw << "; " << "mh: " << mh << endl; int mmh = mh; F0R(i,n){ multiset<int>c,d; F0R(j,m){ if (a[i][j]=='1'){ c.insert(i-dp[0][i][j]+1); d.insert(i+dp[2][i][j]-1); }else{ c.clear(); d.clear(); } if (c.size() == mw){ mmh = min(mmh, *d.begin()-*c.rbegin()+1); c.erase(c.find(i-dp[0][i][j-mw+1]+1)); d.erase(d.find(i+dp[2][i][j-mw+1]-1)); } } } int mmw = mw; F0R(i,m){ multiset<int> c,d; F0R(j,n){ if(a[j][i]=='1'){ c.insert(i-dp[1][j][i]+1); d.insert(i+dp[3][j][i]-1); //cout << j << ' ' << i << "; " << i-dp[1][j][i]+1 << ' ' << i+dp[3][j][i]-1<<endl; }else{ c.clear(); d.clear(); } if (c.size()==mh){ mmw = min(mmw, *d.begin()-*c.rbegin()+1); //cout << j << ' ' << i << ": " << (*d.begin()-*c.rbegin()+1)<<endl; c.erase(c.find(i-dp[1][j-mh+1][i]+1)); d.erase(d.find(i+dp[3][j-mh+1][i]-1)); } } } //cout << mw << ' ' << mmh << "; " << mh << ' ' << mmw << endl; cout << max(mw * mmh, mh * mmw) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...