# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
170234 | theboatman | Bomb (IZhO17_bomb) | C++17 | 47 ms | 7392 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |