Submission #1130313

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

bomb

#include <bits/stdc++.h>
//qwerty47924692
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;
}
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;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            if(can(i,j))ans=max(ans,i*j);
        }
    }
    cout<<ans;

}

• Subtask 1: 30 / 100