제출 #1130754

#제출 시각아이디문제언어결과실행 시간메모리
1130754brover29Bomb (IZhO17_bomb)C++20
0 / 100
1105 ms147764 KiB
#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;
}
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++){
            cout<<can(i,j);
        }
        cout<<'\n';
    }
    ll i=1,j=1;
    while(i<=n&&j<=m){
        if(can(i+1,j))i++;
        else if(can(i,j+1))j++;
        else break;
    }
    cout<<i*j;

}
#Verdict Execution timeMemoryGrader output
Fetching results...