Cod sursa(job #1160550)

Utilizator misinoonisim necula misino Data 30 martie 2014 17:05:03
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<fstream>
#include<stack>
#define N 1010
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n,m,i,sol,j,v[N],p[N][N],a[N],sus[N],jos[N];
stack<int>st;
inline void fa_palind(int a[],int p[]){
    int centru=0,maxi=0;
    for(int i=1;i<=m;++i)
    {
        if(i<=maxi)
        {
            p[i]=min(p[centru*2-i],maxi-i);
            while(i+p[i]+1<=m&&i-p[i]-1>0&&a[i+p[i]+1]==a[i-p[i]-1])
            ++p[i];
            if(i+p[i]>maxi)
            maxi=i+p[i],centru=i;
        }
        else
        {
            while(i+p[i]+1<=m&&i-p[i]-1>=1&&a[i-p[i]-1]==a[i+p[i]+1])
            ++p[i];
            centru=i;
            maxi=i+p[i];
        }
    }
    for(int i=1;i<=m;++i)
    {
        p[i]=p[i]*2+1;
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=m;++j)
        f>>a[j];
        fa_palind(a,p[i]);
    }
    v[0]=v[n+1]=-1;
    for(j=1;j<=m;++j)
    {
        for(i=1;i<=n;++i)
        v[i]=p[i][j];
        st.push(0);
        for(i=1;i<=n;++i)
        {
            while(!st.empty()&&v[st.top()]>=v[i])
            st.pop();
            sus[i]=i-st.top();
            st.push(i);
        }
        while(!st.empty())
        st.pop();
        st.push(n+1);
        for(i=n;i;--i)
        {
            while(!st.empty()&&v[st.top()]>=v[i])
            st.pop();
            jos[i]=st.top()-i;
            st.push(i);
        }
        for(i=1;i<=n;++i)
        sol=max(sol,v[i]*(sus[i]+jos[i]-1));
    }
    g<<sol<<'\n';
    return 0;
}