제출 #170264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
170264		nvmdava	Bomb (IZhO17_bomb)	C++17	38 / 100	384 ms	78492 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];
 
int h[2505], w[2505];
 
vector<pair<int, int> > v;
int pre[N][N];
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(h, 0x3f, sizeof h);
    memset(w, 0x3f, sizeof w);
    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';
            pre[i][j] = pre[i][j - 1] + a[i][j];
        }
    }
    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]);
        }
    }
    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]){
                v.back().ss += t;
                t = v.back().ss;
                v.pop_back();
                if(pre[i + 1][j - 1] - pre[i + 1][j - 1 - t] != t)
                   h[max(up[i][j], v.back().ff) + 1] = min(h[max(up[i][j], v.back().ff) + 1], t);
            }
            if(v.back().ff == up[i][j]){
                v.back().ss += 1 + t;
            } else {
                v.push_back({up[i][j], 1 + t});
            }
        }
    }
 
    int ans = 0;
 
    for(int i = 1; i <= mx; ++i){
        h[i] = min(h[i - 1], h[i]);
        ans = max(ans, h[i] * i);
    }
    cout<<ans;
}

• Subtask 1: 38 / 100