제출 #1258020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258020		proofy	Bomb (IZhO17_bomb)	C++20	100 / 100	718 ms	122932 KiB

bomb

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

const int N = 2503;
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);
    }

    fill(J + 1, J + X + 1, 1e9);

    for (int j = 1; j <= m; j++)  
        for (int i = 1; i <= n; i++)
            if (a[i][j] && !a[i - 1][j]) {
                int pref_L = 1e9, pref_R = 1e9;
                for (int k = i; k < i + D[i][j]; k++) {
                    pref_L = min(pref_L, L[k][j]);
                    pref_R = min(pref_R, R[k][j]);
                    J[1] = min(J[1], L[k][j] + R[k][j] - 1);
                    J[U[k][j]] = min(J[U[k][j]], pref_L + pref_R - 1);
                }
                pref_L = 1e9, pref_R = 1e9;
                for (int k = i + D[i][j] - 1; k >= i; --k) {
                    pref_L = min(pref_L, L[k][j]);
                    pref_R = min(pref_R, R[k][j]);
                    J[D[k][j]] = min(J[D[k][j]], pref_L + pref_R - 1);
                }
            }

    for (int h = 2; h <= X; h++) J[h] = min(J[h], J[h - 1]);

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

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

• Subtask 1: 100 / 100