Submission #1257906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257906		proofy	Bomb (IZhO17_bomb)	C++20	7 / 100	162 ms	6780 KiB

bomb

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

const int N = 453;
int L[N][N], R[N][N], D[N][N][N], J[N], a[N][N], T[N], p;

int Q[N], l, r;

int main() {
	ios::sync_with_stdio(0);
	cin.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';
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) 
            L[i][j] = (a[i][j] ? L[i][j - 1] + 1 : 0);
        for (int j = m; j >= 1; --j)
            R[i][j] = (a[i][j] ? R[i][j + 1] + 1 : 0);
    }

    int X = 1e9;
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) T[i] = (a[i][j] ? T[i - 1] + 1 : 0);
        for (int i = 1; i <= n; i++)
            if (T[i] > 0 && T[i + 1] == 0) X = min(X, T[i]);
    }

    for (int h = 1; h <= X; h++) {
        J[h] = 1e9;
        for (int j = 1; j <= m; j++) { // fix a column j
            p = 0;
            for (int i = 1; i <= n + 1; i++) {
                if (a[i][j]) {
                    T[p++] = L[i][j] + R[i][j] - 1;
                    continue;
                }
                if (p == 0) continue;
                assert(h <= p);

                l = 0, r = -1;

                for (int k = 0; k < p; k++) {
                    while (r >= 0 && T[k] <= T[Q[r]]) --r;
                    Q[++r] = k;
                    if (k >= h - 1) J[h] = min(J[h], T[Q[l]]);
                    if (k >= h) 
                        while (l <= r && Q[l] >= k - h) l++;
                }
                p = 0;
            }
        }
    }

    int ans = 0;
    for (int h = 1; h <= n; h++) ans = max(ans, h * J[h]);

    cout << ans << "\n";
}

• Subtask 1: 7 / 100