Submission #1118849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118849		Younis_Dwai	Bomb (IZhO17_bomb)	C++14	44 / 100	1056 ms	12696 KiB

bomb

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
//#define int long long
#define in insert
//#define mid (l+r)/2
#define in insert
using namespace std;
const int N=2505;
char b[N][N];
int n,m,pref[505][505],d[505][505];
void init(){
     for(int i=1;i<=n;i++){
         for(int j=1;j<=m;j++){
             pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+bool(b[i][j]=='1');
         }
     }
     return ;
}
int query(int x , int y , int x1 , int y1){
    return pref[x1][y1]-pref[x1][y-1]-pref[x-1][y1]+pref[x-1][y-1];
}
int Query(int x , int y , int x1 , int y1){
    return d[x1][y1]-d[x1][y-1]-d[x-1][y1]+d[x-1][y-1];
}
bool ok(int h  , int w){
     for(int i=1;i<=n;i++){
         for(int j=1;j<=m;j++){
             d[i][j]=0;
         }
     }
     for(int i=1;i+h-1<=n;i++){
         for(int j=1;j+w-1<=m;j++){
             if(query(i,j,i+h-1,j+w-1)==h*w){
                d[i][j]=1;
             }
         }
     }
     for(int i=1;i<=n;i++){
         for(int j=1;j<=m;j++){
             d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+d[i][j];
         }
     }
     bool can=1;
     for(int i=1;i<=n;i++){
         for(int j=1;j<=m;j++){
             if(b[i][j]=='1'){
                int i1=max(1,i-h+1),j1=max(1,j-w+1);
                if(Query(i1,j1,i,j)==0) can=0;
             }
         }
     }
     return can;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>b[i][j];
        }
    }
    if(n<=500 && m<=500 && n!=1 && m!=1){
       int mx=0;
       init();
       for(int i=1;i<=n;i++){
           int l=1,r=n,mid=(l+r+1)/2;
           while(l<r){
                 if(ok(i,mid)) l=mid;
                 else r=mid-1;
                 mid=(l+r+1)/2;
           }
           if(ok(i,mid)) mx=max(mx,i*mid);
       }
       cout<<mx;
    }
    else{
        int h=n,w=m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(b[i][j]=='1'){
                   int cnt=1;
                   while(j+1<=m && b[i][j+1]=='1'){
                         ++cnt;
                         ++j;
                   }
                   w=min(w,cnt);
                }
            }
        }
        for(int j=1;j<=m;j++){
            for(int i=1;i<=n;i++){
                if(b[i][j]=='1'){
                   int cnt=1;
                   while(i+1<=n && b[i+1][j]=='1'){
                         ++i;
                         ++cnt;
                   }
                   h=min(h,cnt);
                }
            }
        }
        cout<<h*w;
    }
    return 0;
}

• Subtask 1: 44 / 100