Cod sursa(job #1106990)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 13 februarie 2014 15:40:09
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>
using namespace std;
 ifstream f("dreptpal.in");
 ofstream g("dreptpal.out");
 int n,m,k,d[1005][1005],j,v[1005][1005],x,y,l,r;
  int st[1005],lim[1005][1005],sol=0;

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


   for(i=1;i<=n;i++)
    { x=y=0;
     for(j=1;j<=m;j++)
     {  d[i][j]=1;
      if (j<=y)
       d[i][j]=min(d[i][2*x-j],2*(y-j)+1);

         l=j-d[i][j]/2;
         r=j+d[i][j]/2;

      while(l>1 && r<m && v[i][l-1]==v[i][r+1])
       {l--; r++; d[i][j]+=2;}

      if (r>y)
       { x=j; y=r;}
       //cout<<d[i][j]<<" ";
     }
      //cout<<"\n";
    }

   for(j=1;j<=m;j++)
    { k=0; st[0]=0;
     for(i=1;i<=n;i++)
     {
        while(k && d[i][j]<=d[st[k]][j])
          k--;
         lim[i][j]=i-st[k];

        k++; st[k]=i;
     }
       st[0]=n+1; k=0;

     for(i=n;i>=1;i--)
     {
        while(k && d[i][j]<d[st[k]][j])
          k--;

         lim[i][j]+=st[k]-i-1;

        k++; st[k]=i;
     }

    }


   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      sol=max(sol,lim[i][j]*d[i][j]);

     g<<sol;
    return 0;
}