Cod sursa(job #2156676)

Utilizator Garen456Paun Tudor Garen456 Data 8 martie 2018 21:57:43
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int a[1005][1005],b[1005][1005];
int n,m,stk[1005],top,len[1005];

int main()
{
    fin>>n>>m;
    int i,j,l,r,mid,h,sol=1;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
           fin>>a[i][j];

    for(i=1;i<=n;++i)
    { l=r=mid=1;

        for(j=2;j<=m;++j)
        {  if(j>r)
             l=r=mid=j;
            else
            {  b[i][j]=b[i][mid - (j - mid)];
                if(b[i][j]+j>=r)
                { b[i][j]=r - j;
                    mid=j;
                    l=mid - b[i][j];
                }
            }
            while(l-1 >=1 && r+1 <=m && a[i][l-1]==a[i][r+1])
            { b[i][j]++;
                l--;
                r++;
            }

        }
    }

    for(i=1;i<=n;++i)
          for(j=1;j<=m;++j)
              b[i][j]=b[i][j]*2+1;


    for(j=1;j<=m;++j)
    {  top=0;
        for(i=1;i<=n;++i)
        {   h=0;
            while(top>0 && stk[top-1]>= b[i][j] )
            { h+=len[top-1];
               if(h*stk[top-1] > sol )
                 sol=h*stk[top-1];
               --top;
            }
            stk[top]=b[i][j];
            len[top++]=h+1;
            sol=max(sol,stk[top-1]*len[top-1]);
        }
    }
   fout<<sol;


    return 0;
}