Cod sursa(job #1980569)

Utilizator Bodo171Bogdan Pop Bodo171 Data 13 mai 2017 13:47:10
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=1005;
int a[nmax][nmax],st[nmax][nmax],t[nmax][nmax],u[nmax],s[2*nmax],p[2*nmax];
int n,m,i,j,mx,r,c;
int main()
{
    ifstream f("dreptpal.in");
    ofstream g("dreptpal.out");
    f>>n>>m;
    s[0]=-2;
    for(i=1;i<=m;i++)
        s[2*i-1]=-1;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            f>>s[2*j];
        r=0,c=0;
        for(j=1;j<=2*m;j++)
            p[j]=0;
        for(j=1;j<=2*m;j++)
        {
            if(j<=r)
                p[j]=min(p[2*c-j],r-j);
            while(j-p[j]>=1&&j+p[j]<=2*m&&s[j-p[j]]==s[j+p[j]])
                p[j]++;
        }
        for(j=1;j<=m;j++)
           {a[i][j]=2*((p[2*j]+1)/2)-1;}
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
    {
        while(u[j]>0&&a[i][j]<a[st[j][u[j]]][j])
            u[j]--;
        t[i][j]+=(i-st[j][u[j]]);
        st[j][++u[j]]=i;
    }
    for(j=1;j<=m;j++)
        u[j]=0,st[j][0]=n+1;
    for(i=n;i>=1;i--)
      for(j=1;j<=m;j++)
    {
       while(u[j]>0&&a[i][j]<=a[st[j][u[j]]][j])
            u[j]--;
        t[i][j]+=(st[j][u[j]]-i-1);
        st[j][++u[j]]=i;
      if(t[i][j]*a[i][j]>mx)
        {mx=a[i][j]*t[i][j];}
    }
    g<<mx;
    return 0;
}