Submission #1257933

#TimeUsernameProblemLanguageResultExecution timeMemory
1257933proofyBomb (IZhO17_bomb)C++20
14 / 100
470 ms122748 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 2500;
int L[N][N], R[N][N], U[N][N], D[N][N], a[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;
            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);
    }

    int Y = 1e9;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) if (a[i][j])
            Y = min(Y, L[i][j] + R[i][j] - 1);

    cout << X * Y << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...