Cod sursa(job #2859693)

Utilizator Alex_DiaconuDiaconu Alexandru Alex_Diaconu Data 1 martie 2022 19:25:01
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>

using namespace std;

ifstream cin ("dreptpal.in");
ofstream cout ("dreptpal.out");

const int N=1005;
int a[N][N];
int z[N][N];
int stiva[N];
 
void make_pal(int col, int m)
{
    int c=0, r=0;
    for (int i=1; i<=m; i++)
    {
        int op=2*c-i;
        if (i>r || z[col][op]>=r-i)
        {
            if (i>r)
            {
                r=i;
            }
            int k=r;
            while (k<=m && a[col][k]==a[col][2*i-k])
            {
                k++;
            }
            k--;
            z[col][i]=k-i;
            if (k>r)
            {
                r=k;
                c=i;
            }
        }
        else
        {
            z[col][i]=z[col][op];
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            cin >> a[i][j];
        }
        a[i][0]=-1;
        make_pal(i, m);
    }
    int ans=0;
    for (int i=2; i<m; i++)
    {
        int vf=1;
        stiva[0]=0;
        stiva[1]=0;
        z[n+1][i]=z[0][i]=-1;
        for (int j=1; j<=n+1; j++)
        {
            while (vf && z[j][i]<=z[stiva[vf]][i])
            {
                ans=max(ans, (z[stiva[vf]][i]*2+1)*(j-stiva[vf-1]-1));
                vf--;
            }
            stiva[++vf]=j;
        }
    }
    cout << ans;
}