제출 #973334

#제출 시각아이디문제언어결과실행 시간메모리
973334MilosMilutinovicBomb (IZhO17_bomb)C++14
24 / 100
106 ms81012 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<string> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } vector<vector<int>> U(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (s[i][j] == '0') { continue; } U[i][j] = (i == 0 || s[i - 1][j] == '0' ? i : U[i - 1][j]); } } vector<vector<int>> D(n, vector<int>(m)); for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < m; j++) { if (s[i][j] == '0') { continue; } D[i][j] = (i == n - 1 || s[i + 1][j] == '0' ? i : D[i + 1][j]); } } vector<vector<int>> len(n, vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (s[i][j] == '0') { continue; } len[i][j] = D[i][j] - U[i][j] + 1; } } int width = m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (s[i][j] == '0') { continue; } int ptr = j; while (ptr + 1 < m && s[i][ptr + 1] == '1') { ptr += 1; } width = min(width, ptr - j + 1); j = ptr; } } int height = n; for (int j = 0; j < m; j++) { for (int i = 0; i < n; i++) { if (s[i][j] == '0') { continue; } int ptr = i; while (ptr + 1 < n && s[ptr + 1][j] == '1') { ptr += 1; } height = min(height, ptr - i + 1); i = ptr; } } vector<int> mx(m + 1, height); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (s[i][j] == '0') { continue; } int ptr = j; while (ptr + 1 < m && s[i][ptr + 1] == '1') { ptr += 1; } int mn = (int) 1e9; for (int k = j; k <= ptr; k++) { mn = min(mn, len[i][k]); mx[k - j + 1] = min(mx[k - j + 1], mn); } j = ptr; } } for (int i = 0; i < n; i++) { for (int j = m - 1; j >= 0; j--) { if (s[i][j] == '0') { continue; } int ptr = j; while (ptr > 0 && s[i][ptr - 1] == '1'){ ptr -= 1; } int mn = (int) 1e9; for (int k = j; k >= ptr; k--) { mn = min(mn, len[i][k]); mx[j - k + 1] = min(mx[j - k + 1], mn); } j = ptr; } } for (int i = 1; i < width; i++) { mx[i + 1] = min(mx[i + 1], mx[i]); } int res = 0; for (int i = 1; i <= width; i++) { res = max(res, mx[i] * i); } cout << res << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...