Submission #935445

#	Time	Username	Problem	Language	Result	Execution time	Memory
935445		Darren0724	Bomb (IZhO17_bomb)	C++17	41 / 100	1081 ms	74800 KiB

bomb

#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx","avx2")
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=200005;
int32_t main() {
    LCBorz;
    int n,m;cin>>n>>m;
    vector<vector<int>> v(n+1,vector<int>(m+1,0)),v1(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c;cin>>c;
            v[i][j]=v1[i][j]=(c=='0');
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            v1[i][j]+=v1[i-1][j]+v1[i][j-1]-v1[i-1][j-1];
        }
    }
    long long ans=0;
    int last=0;
    auto check=[&](int a,int b)->int {
        vector<vector<int>> pre(n+2,vector<int>(m+2,0));
        for(int i=a;i<=n;i++){
            for(int j=b;j<=m;j++){
                if(v1[i][j]-v1[i][j-b]-v1[i-a][j]+v1[i-a][j-b]==0){
                    pre[i-a+1][j-b+1]++;
                    pre[i+1][j-b+1]--;
                    pre[i-a+1][j+1]--;
                    pre[i+1][j+1]++;
                }
            }
        }
        int flag=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                pre[i][j]+=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
                if(v[i][j]==0&&pre[i][j]==0){
                    flag=0;
                }
            }
        }
        return flag;
    };
    for(int i=n;i>=1;i--){
        while(last+1<=m&&check(i,last+1)){
            last++;
        }
        ans=max(ans,1ll*last*i);
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 41 / 100