Pagini recente » Momente | Cod sursa (job #1798082) | Politic | test_79 | Cod sursa (job #989984)
Cod sursa(job #989984)
#include <cstdio>
#include <algorithm>
const int MAX_SIZE(1002);
int n, m, Result;
int Matrix [MAX_SIZE] [MAX_SIZE];
int Dp [MAX_SIZE] [MAX_SIZE];
int Stack [MAX_SIZE];
inline void Read (void)
{
std::freopen("dreptpal.in","r",stdin);
std::scanf("%d %d\n",&n,&m);
int i, j;
for (i = 1 ; i <= n ; ++i)
for (j = 1 ; j <= m ; ++j)
std::scanf("%d",&Matrix[i][j]);
std::fclose(stdin);
}
inline void Print (void)
{
std::freopen("dreptpal.out","w",stdout);
std::printf("%d\n",Result);
std::fclose(stdout);
}
inline void Manacher (int *v, int *dp)
{
v[0] = -1;
v[m + 1] = -2;
int i, c(1), r(0), mirror;
for (i = 1 ; i <= m ; ++i)
{
mirror = c - (i - c);
dp[i] = std::min(dp[mirror],r - i);
while (v[i + dp[i] + 1] == v[i - dp[i] - 1])
++dp[i];
if (i + dp[i] > r)
{
c = i;
r = c + dp[c];
}
}
}
inline void Dynamic (void)
{
int i;
for (i = 1 ; i <= n ; ++i)
Manacher(Matrix[i], Dp[i]);
}
inline void Compute (void)
{
int i, j, top, left, right, length;
for (j = 1 ; j <= m ; ++j)
{
top = 0;
for (i = 1 ; i <= n + 1 ; ++i)
{
while (top > 0 && Dp[i][j] <= Dp[Stack[top]][j])
{
left = Stack[top - 1] + 1;
right = i - 1;
length = Dp[Stack[top]][j];
Result = std::max(Result,(right - left + 1) * ((length << 1) + 1));
--top;
}
Stack[++top] = i;
}
}
}
int main (void)
{
Read();
Dynamic();
Compute();
Print();
return 0;
}