제출 #172151

#제출 시각아이디문제언어결과실행 시간메모리
172151MvCBomb (IZhO17_bomb)C++11
50 / 100
1085 ms103928 KiB
//#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<62); const int inf=(1<<30); const int nmax=2505; const int mod=1e9+7; using namespace std; int n,m,i,j,cur,h[nmax][nmax],v[nmax][nmax],x,y,a[nmax][nmax],ad[nmax][nmax],b[nmax][nmax],rs,mid,l,r; char c; bool ok(int h,int w) { int i,j,x; for(i=1;i<=n;i++)for(j=1;j<=m;j++)ad[i][j]=0; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(i<=n-h+1 && j<=m-w+1) { x=b[i+h-1][j+w-1]-b[i+h-1][j-1]-b[i-1][j+w-1]+b[i-1][j-1]; if(x==h*w) { ad[i][j]++; ad[i][j+w]--; ad[i+h][j]--; ad[i+h][j+w]++; } } ad[i][j]+=ad[i-1][j]+ad[i][j-1]-ad[i-1][j-1]; if(!ad[i][j] && a[i][j])return 0; } } return 1; } int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n>>m; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>c; a[i][j]=(c=='1'); b[i][j]=a[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1]; } } x=y=inf; for(i=1;i<=n;i++) { for(j=m;j>=1;j--) { if(a[i][j]) { h[i][j]=h[i][j+1]+1; if(!a[i][j-1])y=min(y,h[i][j]); } } } for(i=1;i<=m;i++) { for(j=n;j>=1;j--) { if(a[j][i]) { v[j][i]=v[j+1][i]+1; if(!a[j-1][i])x=min(x,v[j][i]); } } } if(x==inf)rc(0); if(n*m>=1e6)rc(x*y); for(i=1;i<=x;i++) { l=1,r=y,cur=0; while(l<=r) { mid=(l+r)/2; if(ok(i,mid))cur=mid,l=mid+1; else r=mid-1; } rs=max(rs,i*cur); } cout<<rs<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...