Cod sursa(job #2669590)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 7 noiembrie 2020 12:06:30
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,poz,elem_anterior,lungime,i,j,minim1,minim2,minim,min_sol,v[5010],l[5010];

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

    l[n]=1;
    for(i=n-1;i>=1;i--)
    {
        minim1=INT_MAX;
        minim2=INT_MAX;

        for(j=i+1;j<=n;j++)
        {
            if(v[j]>=v[i] && v[j]<minim1)
            {
                minim1=v[j];
                if(l[j]<minim2)minim2=l[j];
            }
        }

        if(minim2==INT_MAX)l[i]=1;
        else l[i]=minim2+1;
    }

    minim=INT_MAX;
    min_sol=INT_MAX;
    for(i=1;i<=n;i++)
    {
        if(v[i]<minim)
        {
            minim=v[i];
            if(l[i]<min_sol)min_sol=l[i];
        }
    }

    g<<min_sol<<'\n';

    poz=0;
    elem_anterior=INT_MIN;

    for(lungime=min_sol;lungime>=1;lungime--)
    {
        minim=INT_MAX;
        for(i=poz+1;i<=n;i++)
        {
            if(v[i]<minim && v[i]>=elem_anterior)
            {
                minim=v[i];
                if(l[i]==lungime)poz=i;
            }
        }

        g<<poz<<" ";
        elem_anterior=v[poz];
    }
    return 0;
}