Submission #170283

#	Time	Username	Problem	Language	Result	Execution time	Memory
170283		nvmdava	Bomb (IZhO17_bomb)	C++17	40 / 100	376 ms	79788 KiB

bomb

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define N 2505
 
int a[N][N];
int up[N][N], le[N][N];
 
vector<pair<int, int> > v;

int ans[N][N], h[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            char c;
            cin>>c;
            a[i][j] = c - '0';
        }
    }
    int mx=  2500;
    for(int i = 1; i <= m; ++i){
        for(int j = 1; j <= n; ++j){
            if(a[j][i] == 0) up[j][i] = 0;
            else up[j][i] = up[j - 1][i] + 1;
            if(a[j + 1][i] == 0 && a[j][i] == 1)mx = min(mx, up[j][i]);
        }
    }

    memset(ans, 0x3f, sizeof ans);
    memset(h, 0x3f, sizeof h);

    v.push_back({0, 0});
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m + 1; ++j){
            int t = 0;
            while(v.back().ff > up[i][j]){
                t += v.back().ss;
                v.pop_back();
                ans[max(up[i][j], v.back().ff) + 1][i] = min(ans[max(up[i][j], v.back().ff) + 1][i], t);
            }

            if(v.back().ff == up[i][j]){
                v.back().ss += 1 + t;
            } else {
                v.push_back({up[i][j], 1 + t});
            }
        }
    }
 
    int res = 0;
 
    for(int i = 1; i <= mx; ++i){
        for(int j = i; j <= n; j++){
            h[i] = min(h[i], ans[i][j]);
            ans[i + 1][j] = min(ans[i + 1][j], ans[i][j]);
        }
        res = max(res, h[i] * i); 
    }
    cout<<res;
}

• Subtask 1: 40 / 100