Cod sursa(job #1362806)

Utilizator george_stelianChichirim George george_stelian Data 26 februarie 2015 15:39:40
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int v[1010][1010],sol[1010][1010],st[1010],dr[1010],v1[1010];

int max(int a,int b)
{
    if(a>b) return a;
    return b;
}

int main()
{
    freopen("dreptpal.in", "r", stdin);
    freopen("dreptpal.out", "w", stdout);
    int n,m,rez=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) scanf("%d",&v[i][j]);
    for(int i=1;i<=n;i++)
    {
        int mid=1,lim=1;
        for(int j=2;j<=m;j++)
        {
            if(j<=lim) sol[i][j]=min(sol[i][mid-(i-mid)],lim-i);
            while(1<=j-sol[i][j]-1 && j+sol[i][j]+1<=m && v[i][j-sol[i][j]-1]==v[i][j+sol[i][j]+1]) sol[i][j]++;
            if(j+sol[i][j]>lim)
            {
                mid=j;
                lim=sol[i][j];
            }
        }
    }
    for(int j=1;j<=m;j++)
    {
        int nr=0;v1[0]=0;
        for(int i=1;i<=n;i++)
        {
            while(nr && sol[v1[nr]][j]>=sol[i][j]) nr--;
            st[i]=v1[nr];
            v1[++nr]=i;
        }
        nr=0;v1[0]=n+1;
        for(int i=n;i;i--)
        {
            while(nr && sol[v1[nr]][j]>=sol[i][j]) nr--;
            dr[i]=v1[nr];
            v1[++nr]=i;
        }
        for(int i=1;i<=n;i++) rez=max(rez,(sol[i][j]*2+1)*(dr[i]-st[i]-1));
    }
    printf("%d",rez);
    return 0;
}