Cod sursa(job #639802)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 23 noiembrie 2011 22:59:58
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cassert>
#include <cstdio>

inline int max(int x,int y){if (x>y) return x;else return y;}
inline int min(int x,int y){if (x<y) return x;else return y;}

int q[1010],q2[1010],d[1010][1010],v[1010];

int main()
{
    int n,m,i,j,ind,sol=0,cen,cnt,aux;
    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",&v[j]);
        for (j=1,ind=0,cen=0;j<=m;++j)
        {
            if (ind>=j)
                d[i][j]=min(d[i][2*cen-j],2*(ind-j)+1);
            else
                d[i][j]=1;
            while (d[i][j]/2+j<m&&j>d[i][j]/2&&v[j+d[i][j]/2+1]==v[j-d[i][j]/2-1])
                d[i][j]+=2;
            if (j+d[i][j]/2>ind)
            {
                cen=j;
                ind=j+d[i][j]/2;
            }
        }
    }
    for (i=1;i<=m;++i)
    {
        for (cnt=0,j=1;j<=n;++j)
        {
            aux=j;
            while (cnt&&q2[cnt]>d[j][i])
            {
                sol=max(sol,(j-q[cnt])*q2[cnt]);
                aux=q[cnt];
                --cnt;
            }
            ++cnt;
            q[cnt]=aux;
            q2[cnt]=d[j][i];

        }
        for (;cnt;--cnt)
            sol=max(sol,(n-q[cnt]+1)*q2[cnt]);
    }
    printf("%d\n",sol);
    return 0;
}