Cod sursa(job #1471849)

Utilizator andrettiAndretti Naiden andretti Data 15 august 2015 13:46:35
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<stdio.h>
#include<algorithm>
#include<stack>
#define mp make_pair
#define maxn 1005
using namespace std;

int n,m,sol;
int a[maxn][maxn],p[maxn][maxn];
int up[maxn],dw[maxn];
stack< pair<int,int> > s;

void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      scanf("%d",&a[i][j]);
}

int expand(int k,int left,int right)
{
    int nrc=0;
    for(;left && right<=m && a[k][left]==a[k][right];left--,right++)
        nrc++;
    return nrc;
}

void manacher(int k)
{
    int R=0,C;
    int img;

    for(int i=1;i<=m;i++)
    {
        if(R>=i){
            img=2*C-i;
            p[k][i]=min(p[k][img],R-i);
        }
        p[k][i]+=expand(k,i-p[k][i]-1,i+p[k][i]+1);

        if(i+p[k][i]>=R) R=i+p[k][i],C=i;
    }
}

void solve()
{
    for(int i=1;i<=n;i++)
     manacher(i);

    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<=n;i++)
        {
            while(!s.empty() && p[i][j]<s.top().first)
             dw[s.top().second]=i,s.pop();

            s.push(mp(p[i][j],i));
        }
        for(;!s.empty();s.pop()) dw[s.top().second]=n+1;

        for(int i=n;i;i--)
        {
            while(!s.empty() && p[i][j]<s.top().first)
             up[s.top().second]=i,s.pop();

            s.push(mp(p[i][j],i));
        }
        for(;!s.empty();s.pop()) up[s.top().second]=0;

        for(int i=1;i<=n;i++)
         sol=max(sol,(p[i][j]*2+1)*(dw[i]-up[i]-1));
    }
}

int main()
{
    freopen("dreptpal.in","r",stdin);
    freopen("dreptpal.out","w",stdout);

    read();
    solve();
    printf("%d",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}