Cod sursa(job #1212820)

Utilizator nicolaegutaNicolae Guta nicolaeguta Data 26 iulie 2014 00:47:33
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <cstdio>
#include <algorithm>
#define Nmax 1005

using namespace std;

int N,M,a[Nmax][Nmax],Z[Nmax][Nmax],sol,l[Nmax],r[Nmax],st[Nmax];

inline void Manacher(int lin)
{
    int L,Mij,R=0,i,t;
    Z[lin][1]=0;
    for(i=2;i<=M;++i)
        if(i>R)
        {
            Mij=i;
            for(R=i+1;R<=M && a[lin][R]==a[lin][2*Mij-R];++R);
            --R;
            Z[lin][i]=R-Mij;
        }
        else
        {
            t=2*Mij-i; L=2*Mij-R;
            if(Z[lin][t]<t-L)
                Z[lin][i]=Z[lin][t];
            else
            {
                Mij=i;
                for(++R;R<=M && a[lin][R]==a[lin][2*Mij-R];++R);
                --R;
                Z[lin][i]=R-Mij;
            }
        }
}

inline void Stiva(int col)
{
    int top=0,i;
    for(i=1;i<=N;++i)
        r[i]=l[i]=0;
    for(i=1;i<=N;++i)
    {
        while(top && Z[st[top]][col]>Z[i][col])
        {
            r[st[top]]=i;
            --top;
        }
        st[++top]=i;
    }
    for(i=1;i<=N;++i)
        if(!r[i])
            r[i]=N+1;
    top=0;
    for(i=N;i;--i)
    {
        while(top && Z[st[top]][col]>Z[i][col])
        {
            l[st[top]]=i;
            --top;
        }
        st[++top]=i;
    }
}

int main()
{
    int i,j;
    freopen ("dreptpal.in","r",stdin);
    freopen ("dreptpal.out","w",stdout);
    scanf("%d%d", &N,&M);
    for(i=1;i<=N;++i)
        for(j=1;j<=M;++j)
            scanf("%d", &a[i][j]);
    for(i=1;i<=N;++i)
        Manacher(i);
    sol=M;
    for(i=2;i<=M;++i)
    {
        Stiva(i);
        for(j=1;j<=N;++j)
            sol=max(sol,(r[j]-l[j]-1)*(2*Z[j][i]+1));
    }
    printf("%d\n", sol);
    return 0;
}