Submission #764232

#	Time	Username	Problem	Language	Result	Execution time	Memory
764232		someone	Bomb (IZhO17_bomb)	C++14	20 / 100	218 ms	131072 KiB

bomb

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2542, INF = 1e18 + 42;

vector<pair<int, int>> pos[N];
int n, m, val[N][N], occ[N], sz[N][N];

int F(int lig, int col) {
    if(sz[lig][col] < 0)
        return lig * m + col;
    return sz[lig][col] = F(sz[lig][col] / m, sz[lig][col] % m);
}

void U(int l1, int c1, int l2, int c2) {
    int a = F(l1, c1), b = F(l2, c2);
    if(a == b) return;
    occ[-sz[a / m][a % m]]--;
    occ[-sz[b / m][b % m]]--;
    sz[a / m][a % m] += sz[b / m][b % m];
    sz[b / m][b % m] = a;
    occ[-sz[a / m][a % m]]++;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) {
            char c; cin >> c;
            val[i][j] = (int)(c - '0');
            sz[i][j] = -INF;
        }
    for(int i = 0; i < n; i++)
        for(int j = 1; j < m; j++)
            if(val[i][j] == 1)
                val[i][j] += val[i][j-1];

    int bound = INF;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) {
            if(val[i][j] > 0 && val[i][j+1] == 0)
                bound = min(bound, val[i][j]);
            pos[val[i][j]].push_back({i, j});
        }
    if(bound == INF) {
        cout << "0\n";
        return 0;
    }

    int ans = 0;
    for(int i = N-1; i > 0; i--) {
        for(auto pii : pos[i]) {
            occ[1]++;
            int lig = pii.first,
                col = pii.second;
            sz[lig][col] = -1;
            if(0 < lig && val[lig-1][col] >= i && sz[lig-1][col] != -INF)
                U(lig, col, lig-1, col);
            if(lig < n-1 && val[lig+1][col] >= i && sz[lig+1][col] != -INF)
                U(lig, col, lig+1, col);
        }
        if(i <= bound) {
            int mini = 0;
            for(int j = N-1; j > 0; j--)
                if(occ[j])
                    mini = j;
            ans = max(ans, mini * i);
        }
    }
    cout << ans << '\n';
}

• Subtask 1: 20 / 100