Cod sursa(job #2374576)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 7 martie 2019 19:27:22
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<fstream>
#include<queue>
using namespace std;
ifstream fi("dreptpal.in");
ofstream fo("dreptpal.out");
int n,rez,i,A[1005][2005],m,j,k,inv,c,dr,Lp[1005][2005],Pst[1005],pdr,ind;
deque<int> Q;
int main()
{
    fi>>n>>m;
	for(i=1; i<=n; i++)
	{
         ind=0;
         for(j=1; j<=m; j++)
         {
             A[i][++ind]=-1;
             fi>>A[i][++ind];
         }
         A[i][++ind]=-1;
	}
	m=ind;
    for(i=1; i<=n; i++)
    {
        c=0;
        dr=0;
        for(j=1; j<=m; j++)
        {
            if(j<=dr)
            {
                inv=c-(j-c);
                if(inv-Lp[i][inv]>c-Lp[i][c])
                    Lp[i][j]=Lp[i][inv];
                else
                {
                    for(k=dr-j+1; k<=min(j-1,m-j); k++)
                        if(A[i][j+k]!=A[i][j-k])
                            break;
                    Lp[i][j]=k;
                    c=j;
                    dr=j+k-1;
                }
            }
            else
            {
                for(k=1; k<=min(j-1,m-j); k++)
                    if(A[i][j+k]!=A[i][j-k])
                        break;
                Lp[i][j]=k;
                c=j;
                dr=j+k-1;
            }
        }
    }
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            Lp[i][j]=Lp[i][j]/2;
    for(j=1; j<=m; j++)
    {
        Q.clear();
        for(i=1; i<=n; i++)
        {
            while(!Q.empty() && Lp[Q.back()][j]>=Lp[i][j])
                Q.pop_back();
            if(!Q.empty())
                Pst[i]=i-Q.back();
            else
                Pst[i]=i;
            Q.push_back(i);
        }
        Q.clear();
        for(i=n; i>=1; i--)
        {
            while(!Q.empty() && Lp[Q.back()][j]>=Lp[i][j])
                Q.pop_back();
            if(!Q.empty())
                pdr=Q.back()-i-1;
            else
                pdr=n-i;
            Q.push_back(i);
            if(A[1][j]==-1)
                rez=max(rez,(Pst[i]+pdr)*2*Lp[i][j]);
            else
                rez=max(rez,(Pst[i]+pdr)*(2*Lp[i][j]-1));
        }
    }
	fo<<rez<<"\n";
	fi.close();
    fo.close();
    return 0;
}