Submission #1279927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279927		dosts	Bomb (IZhO17_bomb)	C++20	4 / 100	180 ms	196608 KiB

bomb

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;

const int N = 1e5+1;


struct DSU {
    multiset<int> strips;
    vi dad,sz;
    DSU(int m) {
        dad.resize(m);
        sz.assign(m,0);
        iota(all(dad),0ll);
    }
    int find(int x) {
        if (x == dad[x]) return x;
        return dad[x] = find(dad[x]);
    }

    int getstrip(int x) {
        return sz[find(x)];
    }

    void activate(int x) {
        sz[x] = 1;
        strips.insert(1);
    } 

    void merge(int x,int y) {
        int a = find(x),b = find(y);
        assert(a != b);
        strips.erase(strips.find(getstrip(a)));
        strips.erase(strips.find(getstrip(b)));
        dad[a] = b;
        sz[b]+=sz[a];
        strips.insert(getstrip(a));
    }
};

void solve() {
    int n,m;
    cin >> n >> m;
    vector<string> grid(n);
    for (auto& row : grid) cin >> row;
    vector<DSU> dsu(n,DSU(m));
    int h[n][m];
    vector<pii> ppl[n+1];
    for (int i = 0;i<n;i++) {
        for (int j = 0;j<m;j++) {
            if (grid[i][j] == '0') {
                h[i][j] = 0;
                continue;
            }
            if (!i) h[i][j] =1;
            else h[i][j] = h[i-1][j]+1;
            ppl[h[i][j]].push_back({i,j});
        }
    }

    vector<vi> active(n,vi(m,0));
    set<pii> st;
    for (int i = 0;i<n;i++) st.insert({inf,i});
    vi anss(n,inf);
    auto activate = [&](int r,int c) -> void {
        active[r][c] = 1;
        dsu[r].activate(c);
        st.erase({anss[r],r});
        if (c && active[r][c-1]) dsu[r].merge(c-1,c);
        if (c<m-1 && active[r][c+1]) dsu[r].merge(c,c+1);
        anss[r] = *dsu[r].strips.begin();
        st.insert({anss[r],r});
    };

    int ans = 0;
    for (int i = n;i>=1;i--) {
        for (auto it : ppl[i]) {
            activate(it.ff,it.ss);
        }
        if (st.begin()->first != inf) ans = max(ans,i*st.begin()->first);
    }
    cout << ans << '\n';


}   

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

• Subtask 1: 4 / 100