Cod sursa(job #2761005)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 30 iunie 2021 01:02:32
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("dreptpal.in");
ofstream g("dreptpal.out");

int n,m;
int v[1005][1005],manacher[1005][1005];
int aux[1005],st[1005],dr[1005],stiva[1005];
int ans=0;

void compute_manacher(int ind)
{
    int l=0,r=0;

    for(int i=1; i<=m; i++)
    {
        int k;
        if( i>r ) k=1;
        else k=min( manacher[ind][l+r-i],r-i+1 );

        while( i-k>=1&&i+k<=m&&v[ind][i-k]==v[ind][i+k] )
        {
            k++;
        }

        manacher[ind][i]=k;
        k--;

        if( i+k>r )
        {
            l=i-k;
            r=i+k;
        }
    }
}

void solve(int ind)
{
    for(int i=1;i<=n;i++) aux[i]=manacher[i][ind],st[i]=dr[i]=0;

    int nr;

    for(int i=1;i<=n;i++)
     if(i==1) nr=1,stiva[1]=1;
     else
     {
        while( nr&&aux[i]<aux[stiva[nr]] )
        {
         dr[stiva[nr]]=i;
         nr--;
        }
        stiva[++nr]=i;
     }

    for(int i=1;i<=nr;i++) dr[stiva[i]]=n+1;

    for(int i=n;i>=1;i--)
     if(i==n) nr=1,stiva[1]=n;
     else
     {
        while( nr&&aux[i]<aux[stiva[nr]] )
        {
         st[stiva[nr]]=i;
         nr--;
        }
        stiva[++nr]=i;
     }

    for(int i=1;i<=n;i++)
    {
     int latime=dr[i]-st[i]-1;
     int lungime=aux[i]*2-1;

     ans=max(ans,latime*lungime);
    }
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            f>>v[i][j];

    for(int i=1; i<=n; i++)
        compute_manacher(i);

    for(int i=1;i<=m;i++)
        solve(i);

    g<<ans;
}