Submission #689578

#	Time	Username	Problem	Language	Result	Execution time	Memory
689578		azimanov	Bomb (IZhO17_bomb)	C++17	24 / 100	184 ms	110820 KiB

bomb

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2500 + 10;
bool a[N][N];
int l[N][N], u[N][N];
int r[N][N], d[N][N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char ch;
            cin >> ch;
            a[i][j] = ch == '1';
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j]) {
                l[i][j] = l[i][j - 1] + 1;
                u[i][j] = u[i - 1][j] + 1;
            }
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = m; j >= 1; j--) {
            if (a[i][j]) {
                r[i][j] = r[i][j + 1] + 1;
                d[i][j] = d[i + 1][j] + 1;
            }
        }
    }
    int mx_h = n, mx_w = m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j]) {
                mx_h = min(mx_h, u[i][j] + d[i][j] - 1);
                mx_w = min(mx_w, l[i][j] + r[i][j] - 1);
            }
        }
    }
    cout << mx_h * mx_w << "\n";

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}

• Subtask 1: 24 / 100