Cod sursa(job #989984)

Utilizator primulDarie Sergiu primul Data 27 august 2013 08:33:19
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#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;
}