# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1127880 | Tsagana | Bomb (IZhO17_bomb) | C++17 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
int a[2505][2505];
int L[2505][2505];
int R[2505][2505];
int ans[2505];
void solve () {
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++) ans[i] = m;
int lim = n;
for (int rep = 0; rep < 2; rep++) {
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; else L[i][j] = 0;
for (int j = m; j >= 1; j--) if (a[i][j]) R[i][j] = R[i][j + 1] + 1; else R[i][j] = 0;
for (int j = 1; j <= m; j++) if (a[i][j]) ans[1] = min(ans[1], L[i][j] + R[i][j] - 1);
}
for (int j = 1; j <= m; j++) {
int cnt = 0, LX = -1, RX = -1;
for (int i = 1; i <= n+1; i++) {
if (a[i][j]) {
cnt++; if (cnt == 1) {LX = L[i][j]; RX = R[i][j];}
LX = min(LX, L[i][j]);
RX = min(RX, R[i][j]);
ans[cnt] = min(ans[cnt], LX + RX - 1);
}
else {
if (cnt > 0) lim = min(lim, cnt);
LX = RX = -1;
cnt = 0;
}
}
}
for (int i = 1; i <= n / 2; i++)
for (int j = 1; j <= m; j++)
swap(a[i][j], a[n - i+1][j]);
}
int res = 0;
for (int i = 1; i <= lim; i++) {
ans[i+1] = min(ans[i+1], ans[i]);
res = max(res, ans[i]*i);
}
cout << res;
}
signed main() {IOS solve(); return 0;}