#include"bits/stdc++.h"
using namespace std;
using ll=long long;
template<class T>using v=vector<T>;
using vi=v<int>;
#define sz(x)int(size(x))
#define all(x)begin(x),end(x)
#define rall(x)rbegin(x),rend(x)
#define lb lower_bound
#define ub upper_bound
template<class T>int lwb(v<T>&a,T b) {
return int(lb(all(a),b)-begin(a));
}
template<class T>int lwb(T a[],int n,T b) {
return int(lb(a,a+n,b)-a);
}
template<class T>int upb(v<T>&a,T b) {
return int(ub(all(a),b)-begin(a));
}
template<class T>int upb(T a[],int n,T b) {
return int(ub(a,a+n,b)-a);
}
#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;(a)<=i;i--)
#define R0F(i,a)ROF(i,0,a)
#define rep(a)F0R(_,a)
const int mxN = 2503;
int ph[mxN][mxN];
int pv[mxN][mxN];
int g[mxN][mxN];
main() {
int N, M;
cin >> N >> M;
FOR(i, 1, N + 1) {
FOR(j, 1, M + 1) {
char c; cin >> c;
g[i][j] = c - '0';
}
}
FOR(i, 1, N + 1) {
FOR(j, 1, M + 1) {
ph[i][j] = ph[i][j - 1] + g[i][j];
pv[i][j] = pv[i - 1][j] + g[i][j];
}
}
int l = 1, r = N;
while (l < r) {
int mi = (l + r + 1) / 2;
int f = 1;
FOR(i, 1, N + 1) {
FOR(j, 1, M + 1) {
int k = i + mi - 1;
if (0 == g[i - 1][j] && 1 == g[i][j] && (k > N || mi != pv[k][j] - pv[i - 1][j])) {
f = 0;
}
}
}
if (f) {
l = mi;
} else {
r = mi - 1;
}
}
int height = l;
l = 1, r = N;
while (l < r) {
int mi = (l + r + 1) / 2;
int f = 1;
FOR(i, 1, N + 1) {
FOR(j, 1, M + 1) {
int k = j + mi - 1;
if (0 == g[i][j - 1] && 1 == g[i][j] && (k > M || mi != ph[i][k] - pv[i][j - 1])) {
f = 0;
}
}
}
if (f) {
l = mi;
} else {
r = mi - 1;
}
}
int width = l;
cout << height * width << endl;
}
Compilation message (stderr)
bomb.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
35 | main() {
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |