Cod sursa(job #636907)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 20 noiembrie 2011 01:18:33
Problema DreptPal Scor 90
Compilator cpp Status done
Runda .com 2011 Marime 1.27 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],d[1010][1010],v[1010];

int main()
{
    int n,m,i,j,ind,sol=0,cen,cnt;
    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+1<=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)
        {
            while (cnt&&d[q[cnt]][i]>d[j][i])
            {
                sol=max(sol,(j-q[cnt])*d[q[cnt]][i]);
                --cnt;
            }
            ++cnt;
            q[cnt]=j;
        }
        for (;cnt;--cnt)
            sol=max(sol,(n-q[cnt]+1)*d[q[cnt]][i]);
    }
    printf("%d\n",sol);
    return 0;
}