제출 #173274

#제출 시각아이디문제언어결과실행 시간메모리
173274apostoldaniel854Bomb (IZhO17_bomb)C++14
74 / 100
529 ms61560 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2500; char a[1 + N][1 + N]; int lst[1 + N + 1][1 + N + 1]; int nxt[1 + N + 1][1 + N + 1]; int best[1 + N]; int main () { // freopen ("bomb.in", "r", stdin); // freopen ("bomb.out", "w", stdout); ios::sync_with_stdio (false); cin.tie (0); cout.tie (0); int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j], a[i][j] -= '0'; int mxl = n; for (int j = 1; j <= m; j++) for (int i = 1; i <= n; i++) { if (a[i][j] == 0) continue; int k = i; while (k <= n && a[k + 1][j] == 1) k++; mxl = min (mxl, k - i + 1); i = k; } int mxc = m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (a[i][j] == 0) continue; int k = j; while (k <= m && a[i][k + 1] == 1) k++; mxc = min (mxc, k - j + 1); j = k; } for (int i = 1; i <= n; i++) { lst[i][0] = 1; for (int j = 1; j <= m; j++) { lst[i][j] = lst[i][j - 1]; if (a[i][j] == 0) lst[i][j] = j + 1; } nxt[i][m + 1] = m; for (int j = m; j > 0; j--) { nxt[i][j] = nxt[i][j + 1]; if (a[i][j] == 0) nxt[i][j] = j - 1; } } for (int i = 1; i <= n; i++) best[i] = m + 1; for (int j = 1; j <= m; j++) { int cur = 0; int l = 0, r = m + 1; for (int i = 1; i <= n; i++) { if (a[i][j] == 0) cur = 0; else { cur++; l = max (l, lst[i][j]); r = min (r, nxt[i][j]); best[cur] = min (best[cur], r - l + 1); } } cur = 0; l = 0, r = m + 1; for (int i = n; i > 0; i--) { if (a[i][j] == 0) cur = 0; else { cur++; l = max (l, lst[i][j]); r = min (r, nxt[i][j]); best[cur] = min (best[cur], r - l + 1); } } } int ans = 0; for (int i = 1; i <= mxl; i++) ans = max (ans, min (mxc, best[i]) * i); cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...