Submission #936266

#	Time	Username	Problem	Language	Result	Execution time	Memory
936266		guagua0407	Bomb (IZhO17_bomb)	C++17	100 / 100	143 ms	74320 KiB

bomb

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=2505;
const int inf=1e9;
int c[mxn][mxn];
int up[mxn][mxn];
int down[mxn][mxn];
int n,m;
int ans[mxn];

void sir(){
    for(int i=1;i<=n;i++){
        for(int l=1;l<=m;l++){
            if(!c[i][l]) continue;
            int r=l;
            while(r<=m and c[i][r]) r++;
            int a=inf,b=inf;
            for(int x=l;x<r;x++){
                a=min(a,up[i][x]);
                b=min(b,down[i][x]);
                ans[x-l+1]=min(ans[x-l+1],a+b-1);
            }
            //cout<<i<<' '<<l<<' '<<r-1<<' '<<a<<' '<<b<<'\n';
            l=r-1;
        }
    }
}

int main() {_
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char cur;
            cin>>cur;
            c[i][j]=(cur=='1');
            //cout<<c[i][j];
        }
        //cout<<'\n';
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(c[i][j]) up[i][j]=up[i-1][j]+1;
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            if(c[i][j]) down[i][j]=down[i+1][j]+1;
        }
    }
    int mn=inf;
    for(int j=1;j<=m;j++){
        for(int l=1;l<=n;l++){
            if(!c[l][j]) continue;
            int r=l;
            while(r<=n and c[r][j]) r++;
            mn=min(mn,r-l);
            l=r-1;
        }
    }
    for(int i=1;i<=m;i++){
        ans[i]=mn;
    }
    sir();
    for(int i=1;i<=n;i++){
        reverse(c[i]+1,c[i]+m+1);
        reverse(up[i]+1,up[i]+m+1);
        reverse(down[i]+1,down[i]+m+1);
    }
    sir();
    mn=inf;
    for(int i=1;i<=n;i++){
        for(int l=1;l<=m;l++){
            if(!c[i][l]) continue;
            int r=l;
            while(r<=m and c[i][r]) r++;
            mn=min(mn,r-l);
            l=r-1;
        }
    }
    int mx=0;
    for(int i=1;i<=mn;i++){
        mx=max(mx,i*ans[i]);
    }
    cout<<mx<<'\n';
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message (stderr)

bomb.cpp: In function 'void setIO(std::string)':
bomb.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bomb.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100