Submission #170234

#TimeUsernameProblemLanguageResultExecution timeMemory
170234theboatmanBomb (IZhO17_bomb)C++17
24 / 100
47 ms7392 KiB
#include <bits/stdc++.h> #define y1 theboatman #define make_struct(args...) {args} using namespace std; typedef long long ll; const long long INF = ll(1e18) + 10; const int inf = int(1e9) + 10; const int N = int(1e6) + 10; bool can(int first, int c, int n, int m, vector <string> &a) { for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if (a[i][j] == '1') { int sz = 0; while(j < m && a[i][j] == '1') { j++; sz++; } j--; if (sz < c) { return false; } } } } for(int j = 0; j < m; j++) { for(int i = 0; i < n; i++) { if (a[i][j] == '1') { int sz = 0; while(i < n && a[i][j] == '1') { i++; sz++; } i--; if (sz < first) { return false; } } } } return true; } void brute(int n, int m) { vector <string> a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } ll ans = 0; for(int first = 1; first <= n; first++) { for(int second = 1; second <= m; second++) { if (can(first, second, n, m, a)) { ans = max(ans, 1LL * first * second); } else { break; } } } cout << ans << "\n"; } int main() { cin.tie(0); ios::sync_with_stdio(0); int n, m; cin >> n >> m; if (1LL * n * m * n * m <= int(5e7)) { brute(n, m); return 0; } vector <string> a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } int second = m; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if (a[i][j] == '1') { int sz = 0; while(j < m && a[i][j] == '1') { j++; sz++; } j--; second = min(second, sz); } } } int first = n; for(int j = 0; j < m; j++) { for(int i = 0; i < n; i++) { if (a[i][j] == '1') { int sz = 0; while(i < n && a[i][j] == '1') { i++; sz++; } i--; first = min(first, sz); } } } cout << 1LL * first * second << "\n"; return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...