Cod sursa(job #2491437)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 12 noiembrie 2019 16:43:52
Problema Subsir 2 Scor 36
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("subsir2.in");
ofstream g("subsir2.out");

int n,i,lungime,maxi,j,ok,indice,maxim,sol[5010],l[5010],v[5010];

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

    l[n]=1;
    for(i=n-1;i>=1;i--)
    {
        maxim=0;
        for(j=i+1;j<=n;j++)
            if(v[j]>=v[i] && l[j]>maxim)maxim=l[j];

        l[i]=maxim+1;
        if(l[i]>maxi)maxi=l[i];
    }

    indice=0;
    lungime=maxi;
    ok=1;

    v[0]=INT_MAX;

    for(i=1;i<=n;i++)
    {
        if(l[i]==maxi)
        {
            lungime=maxi;indice=0;
        }

        if(l[i]==lungime)
        {
            lungime--;
            indice++;
            if(v[sol[indice]]>v[i] && ok==1) sol[indice]=i;
            else if(v[sol[indice]]<v[i]) ok=0;

            if(lungime==0){lungime=maxi;indice=0;}
        }
    }

    g<<maxi<<'\n';

    for(i=1;i<=maxi;i++)
        g<<sol[i]<<" ";

    return 0;
}