Submission #1130321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130321		brover29	Bomb (IZhO17_bomb)	C++20	28 / 100	1104 ms	147768 KiB

bomb

#include <bits/stdc++.h>
//qwerty47924692
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using namespace std;
using ll = long long;
const ll N=2509;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second

ll n,m,a[N][N],used[N][N],pref[N][N];
ll calc(ll xa,ll ya,ll xb,ll yb){
    return pref[xb][yb]-pref[xa-1][yb]-pref[xb][ya-1]+pref[xa-1][ya-1];
}
bool can(ll x,ll y){
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            used[i][j]=0;
        }
    }
    for(ll i=1;i+x-1<=n;i++){
        for(ll j=1;j+y-1<=m;j++){
            if(a[i][j]==1&&calc(i,j,i+x-1,j+y-1)==x*y){
                used[i][j]++;
                used[i][j+y]--;
                used[i+x][j]--;
                used[i+x][j+y]++;
            }
        }
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            used[i][j]+=used[i-1][j]+used[i][j-1]-used[i-1][j-1];
            if(a[i][j]==1&&!used[i][j])return 0;
        }
    }
    return 1;
}
ll check(ll i){
    ll l=0,r=m;
    while(l<r){
        ll mid=(r+l+1)>>1;
        if(can(i,mid))l=mid;
        else r=mid-1;
    }
    return l*i;

}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            char c;
            cin>>c;
            a[i][j]=c-'0';
            pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
        }
    }ll ans=0;
    ll l=1,r=n;
    for(ll i=1;i<=15;i++){
        ll m1=l+(r-l)/3;
        ll m2=r-(r-l)/3;
        if(check(m1)<check(m2))l=m1;
        else r=m2;
    }
    for(ll i=l;i<=r;i++)ans=max(ans,check(i));
    cout<<ans;

}

• Subtask 1: 28 / 100