#include<bits/stdc++.h>
using namespace std;
const int N = 2505;
int n, m, Mnx, R[N], up[N][N], dn[N][N];
int qu[N], F[N];
char A[N][N];
inline int Calc(int lenx)
{
if (lenx > Mnx)
return 0;
int Mn = n;
for (int i = 1; i <= n; i++)
{
int l = 0, r = 0;
for (int j = 1; j <= m; j++)
{
while (r - l && dn[i][j] <= dn[i][qu[r-1]])
r --;
qu[r ++] = j;
if (qu[l] <= j - lenx)
l ++;
F[j - lenx + 1] = dn[i][qu[l]] - 1;
}
l = r = 0;
for (int j = 1; j <= m; j++)
{
while (r - l && up[i][j] >= up[i][qu[r-1]])
r --;
qu[r ++] = j;
if (qu[l] <= j - lenx)
l ++;
F[j - lenx + 1] -= up[i][qu[l]];
}
l = r = 0;
for (int j = 1; j <= m; j++)
{
if (j + lenx - 1 <= m)
{
F[j] = max(F[j], 0);
while (r - l && F[j] >= F[qu[r-1]])
r --;
qu[r ++] = j;
}
while (qu[l] <= j - lenx)
l ++;
if (A[i][j] == '1')
Mn = min(Mn, F[qu[l]]);
}
}
return (Mn);
}
inline void Init()
{
Mnx = m;
for (int i = 1; i <= n; i++)
{
int last = 0;
for (int j = 1; j <= m; j++)
if (A[i][j] == '0')
{
if (last != j - 1)
Mnx = min(Mnx, j - last - 1);
last = j;
}
if (last != m)
Mnx = min(Mnx, m - last);
}
}
void Solve(int l = 1, int r = Mnx)
{
if (r - l + 1 <= 2)
return ;
if (R[l] == R[r])
{
for (int i = l + 1; i < r; i++)
R[i] = R[l];
return ;
}
int md = (l + r) >> 1;
R[md] = Calc(md);
Solve(l, md);
Solve(md, r);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%s", &A[i][1]);
Init();
if (1LL n * m * m >= 1000 * 1000 * 1000)
return !printf("No thanks.");
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
up[i][j] = i - 1;
if (A[i - 1][j] == '1')
up[i][j] = up[i - 1][j];
}
for (int i = n; i; i--)
for (int j = 1; j <= m; j++)
{
dn[i][j] = i + 1;
if (A[i + 1][j] == '1')
dn[i][j] = dn[i + 1][j];
if (A[i][j] == '0')
dn[i][j] = 0, up[i][j] = n + 1;
}
R[1] = Calc(1);
R[Mnx] = Calc(Mnx);
Solve(1, Mnx);
set < int > S;
for (int i = 1; i <= Mnx; i++)
S.insert(R[i]);
if ((int)S.size() >= 50)
assert(0);
int Mx_s = 0;
for (int i = 1; i <= Mnx; i++)
Mx_s = max(Mx_s, i * R[i]);
return !printf("%d", Mx_s);
}
Compilation message
bomb.cpp: In function 'int main()':
bomb.cpp:92:13: error: expected ')' before 'n'
if (1LL n * m * m >= 1000 * 1000 * 1000)
^
bomb.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
bomb.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", &A[i][1]);
~~~~~^~~~~~~~~~~~~~~~
