Cod sursa(job #2460993)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 24 septembrie 2019 19:46:13
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;
const int nmax=1005;
int a[nmax][nmax],man[nmax][nmax],aux[nmax],l[nmax];
void Manacher(int n,int m)
{
    for (int i=1;i<=n;i++)
    {
        int st=0,dr=0;
        for (int j=1;j<=m;j++)
        {
            if(j <= dr)
                man[i][j]=min(man[i][2*st-j],dr-j);
            int ca=man[i][j];
            while(j-ca>1 and j+ca<m and a[i][j-ca-1]==a[i][j+ca+1])
                {
                    man[i][j]++;
                    ca++;
                }
            if(j+man[i][j]>dr)
                st=j,dr=j+man[i][j];
        }
    }
}
int main()
{
    ifstream cin("dreptpal.in");
    ofstream cout("dreptpal.out");
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    Manacher(n,m);
    int ans = 0;
    for (int j=1;j<=m;j++)
    {
        for (int i=1;i<=n;i++)
        {
            int k=i-1;
            while(k>=1 and man[k][j]>=man[i][j])
                k=aux[k];
            aux[i]=k;
            l[i]=i-k;
        }
        for (int i=n;i>=1;i--)
        {
            int k=i+1;
            while(k<=n and man[k][j]>=man[i][j])
                k=aux[k];
            aux[i]=k;
            l[i]=l[i]+k-i;
        }
        for (int i=1;i<=n;i++)
            ans=max(ans,(l[i]-1)*(2*man[i][j]+1));
    }
    cout<<ans<<"\n";
    return 0;
}