Cod sursa(job #1391398)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 17 martie 2015 21:52:47
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int N,M,Matrix[1005][1005],DP[1005][1005],Stack[1005],Left[1005],Right[1005];
int ans;
int Expand(int Left,int Right,int line)
{
    int length=0;
    while(Left>=1 && Right<=M && Matrix[line][Left]==Matrix[line][Right])
    {
        length++;
        Left--;
        Right++;
    }
    return length;
}
void precalcDP(int line)
{
    int i,R=0,P=0,Left,Right;
    for(i=1;i<=M;i++)
    {
        if(R>=i)
            DP[line][i]=min(R-i,DP[line][P-(i-P)]);
        Left=i-DP[line][i];
        Right=i+DP[line][i];
        DP[line][i]+=Expand(Left,Right,line);
        if(DP[line][i]+i>R)
        {
            R=DP[line][i]+i;
            P=i;
        }
    }
}
void Read()
{
    f>>N>>M;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            f>>Matrix[i][j];
    for(int i=1;i<=N;i++)
        precalcDP(i);
}

void precalcLeft(int col)
{
    Stack[0]=0;
    for(int j=N;j>=1;j--)
    {
        while(Stack[0]!=0 && DP[Stack[Stack[0]]][col]>DP[j][col])
        {
            Left[Stack[Stack[0]]]=j;
            --Stack[0];
        }
        Stack[++Stack[0]]=j;
    }
}
void precalcRight(int col)
{
    Stack[0]=0;
    for(int j=1;j<=N;j++)
    {
        Right[j]=N+1;
        while(Stack[0]!=0 && DP[Stack[Stack[0]]][col]>DP[j][col])
        {
            Right[Stack[Stack[0]]]=j;
            --Stack[0];
        }
        Stack[++Stack[0]]=j;
    }
}
void countResult()
{
    for(int i=1;i<=M;i++)
    {
        precalcLeft(i);
        precalcRight(i);
        for(int j=1;j<=N;j++)
            ans=max(ans,(Right[j]-Left[j]-1)*(2*DP[j][i]-1));
    }
    g<<ans<<"\n";
}
int main()
{
    Read();
    countResult();
    return 0;
}