Submission #337895

#	Time	Username	Problem	Language	Result	Execution time	Memory
337895		BY_KUTBILIM	Bomb (IZhO17_bomb)	C++14	68 / 100	494 ms	112496 KiB

bomb

/** @BY_KUTBILIM **/
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define ll long long
#define all(x) ((x).begin(), (x).end())
#define rall(x) ((x).rbegin(), (x).end())

const int inf = (int)1e9+7;

int up[2510][2510], down[2510][2510];

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

    int n, m;
    cin >> n >> m;
    bool a[n][m];
    char ch;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> ch;
            a[i][j] = bool(ch - '0');
        }
    }
    int W = m, H = n, len;
    for(int i = 0; i < n; i++){
        len = 0;
        for(int j = 0; j < m; j++){
            if(a[i][j])len++;
            else{
                if(len)W = min(W, len);
                len = 0;
            }
        }
        if(len)W = min(W, len);
    }
    for(int j = 0; j < m; j++){
        len = 0;
        for(int i = 0; i < n; i++){
            if(a[i][j])len++;
            else{
                if(len)H = min(H, len);
                len = 0;
            }
        }
        if(len)H = min(H, len);
    }
    
    for(int j = 0; j < m; j++){
        for(int i = 0; i < n; i++){
            if(a[i][j]){
                up[i][j] = (i ? up[i-1][j] : 0) + 1;
            }
        }
        for(int i = n - 1; i >= 0; i--){
            if(a[i][j]){
                down[i][j] = (i < n - 2 ? down[i+1][j] : 0) + 1;
            }
        }
    }
    
    vector<int> ans(W, H);
    int l, r;
    for(int i = 0; i < n; i++){
        l = inf, r = inf, len = 0;
        for(int j = 0; j < m; j++){
            if(a[i][j]){
                r = min(r, up[i][j]);
                l = min(l, down[i][j]);
                ans[len] = min(ans[len], r + l - 1);
                len++;
            } else len = 0, l = inf, r = inf;
        }
        for(int j = m - 1; j >= 0; j--){
            if(a[i][j]){
                r = min(r, up[i][j]);
                l = min(l, down[i][j]);
                ans[len] = min(ans[len], r + l - 1);
                len++;
            } else len = 0, l = inf, r = inf;
        }
    }
    int res = ans[0];
    for(int i = 1; i < W; i++){
        ans[i] = min(ans[i], ans[i-1]);
        res = max(res, ans[i] * (i+1));
    }
    cout << res;

    return 0;
}

• Subtask 1: 68 / 100