Submission #1258014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258014		proofy	Bomb (IZhO17_bomb)	C++20	21 / 100	443 ms	4704 KiB

bomb

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

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

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++)
            U[i][j] = (a[i][j] ? U[i - 1][j] + 1 : 0);
        for (int i = n; i >= 1; --i)
            D[i][j] = (a[i][j] ? D[i + 1][j] + 1 : 0);

        for (int i = 1; i <= n; i++) if (a[i][j])
            X = min(X, U[i][j] + D[i][j] - 1);
    }

    for (int h = 1; h <= X; h++) {
        J[h] = 1e9;
        for (int j = 1; j <= m; j++) { // fix a column j
            
            for (int i = 1; i <= n; i++)
                if (a[i][j] && !a[i - 1][j]) {
                    deque<int> dq_R, dq_L;
                    for (int k = i; k < i + D[i][j]; k++) {
                        while (!dq_R.empty() && dq_R.front() <= k - h) dq_R.pop_front();
                        while (!dq_L.empty() && dq_L.front() <= k - h) dq_L.pop_front();

                        while (!dq_R.empty() && R[dq_R.back()][j] >= R[k][j]) dq_R.pop_back();
                        while (!dq_L.empty() && L[dq_L.back()][j] >= L[k][j]) dq_L.pop_back();
                        dq_R.push_back(k);
                        dq_L.push_back(k);

                        if (U[k][j] >= h) T[U[k][j] - h + 1] = L[dq_L.front()][j] + R[dq_R.front()][j] - 1;
                    }

                    deque<int> dq;
                    for (int k = i; k + h - 1 < i + D[i][j]; k++) {
                        while (!dq.empty() && dq.front() <= k - h) dq.pop_front();

                        while (!dq.empty() && T[dq.back()] <= T[U[k][j]]) dq.pop_back();
                        dq.push_back(U[k][j]);
                        
                        J[h] = min(J[h], T[dq.front()]);
                    }
                }
        }
    }

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

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

• Subtask 1: 21 / 100