제출 #1257372

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

bomb

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

const int N = 2512;
int s[N][N];

int next_one[N][N], prev_one[N][N], up[N][N], down[N][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;
            s[i][j] = c - '0';
        }
    
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; --j) if (s[i][j])
            next_one[i][j] = (s[i][j + 1] ? next_one[i][j + 1] : j + 1);
        for (int j = 1; j <= m; j++) if (s[i][j])
            prev_one[i][j] = (s[i][j - 1] ? prev_one[i][j - 1] : j - 1);
    }

    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) if (s[i][j])
            up[i][j] = (s[i - 1][j] ? up[i - 1][j] : i - 1);
        for (int i = n; i >= 1; --i) if (s[i][j])
            down[i][j] = (s[i + 1][j] ? down[i + 1][j] : i + 1);
    }

    int inf = 1e9;
    int best_width = inf, best_height = inf;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) if (s[i][j]) {
            best_height = min(best_height, down[i][j] - up[i][j] - 1);
            best_width = min(best_width, next_one[i][j] - prev_one[i][j] - 1);
        }

    assert(best_width < inf && best_height < inf);

    cout << best_width * best_height << "\n";
}

• Subtask 1: 24 / 100