Cod sursa(job #1016240)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 25 octombrie 2013 22:31:10
Problema DreptPal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <vector>
#define Nmax 1099
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");

int M,n,N,arie;
vector < int > T,P;
vector < int > Sol[Nmax];

inline void Preprocess(vector < int > &T)
{
    //din "1234" fac "-99 -1 1 -1 2 -1 3 -1 4 - 88"
    T.clear();
    T.pb(-99);T.pb(-1);
    for(int i=1;i<=N;++i)
    {
        int x;
        f>>x;
        T.pb(x);T.pb(-1);
    }
    T.pb(-88);
    N*=2;
}

inline int FindLPS(vector < int > T, vector < int > &P)
{
    int C=0,R=0;
    P.clear();
    P.resize(P.size()+N+5);
    for(int i=1;i<=N;++i)
    {
        int i_mirror=2*C-i;
        if(R>i)P[i]=min(R-i,P[i_mirror]);
            else P[i]=0;
        while(T[i+1+P[i]] == T[i-1-P[i]])++P[i];
        if(i+P[i]>R)
        {
            C=i;
            R=i+P[i];
        }
    }
}

inline void PrintLPS(vector < int > P,vector < int > &Sol)
{
    Sol.resize(Sol.size()+N/2+5);
    for(int i=1;i<=N;++i)
        if(i%2==0)
        {
            while(P[i]>=1)
            {
                int st=(i-1-P[i])/2;
                Sol[st+1]=P[i];
                P[i]-=2;
            }
        }
}
int main()

{
    f>>M>>n;
    for(int i=1;i<=M;++i)
    {
        N=n;
        Preprocess(T);
        FindLPS(T,P);
        PrintLPS(P,Sol[i]);
    }
    for(int j=1;j<=n;++j)
    {
        int val=0,k=1;
        for(int i=1;i<=M;++i)
            if(Sol[i][j]!=val && Sol[i][j]%2==1)
            {
                if(k*val>arie)arie=k*val;
                k=1; val=Sol[i][j];
            }
            else ++k;
    }
    g<<arie<<'\n';
    f.close();g.close();
    return 0;
}