Cod sursa(job #2669394)

Utilizator monica_LMonica monica_L Data 6 noiembrie 2020 21:02:04
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
//https://www.infoarena.ro/problema/subsir2

#include <fstream>
# define M 1000000
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
long long n,i,v[5001],l[5001],mx,x,mn,mx1,j,poz;
int main()
{
    f>>n;
    for(i=1; i<=n; i++)
        f>>v[i];

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

            }
        if(l[i]==M)l[i]=1;
    }

    mx=M;
    mn=M;

    for(i=1; i<=n; i++)
        if(v[i]<mn)
        {
            mn=v[i];
            mx=min(mx,l[i]);
        }

    g<<mx<<'\n';

    x=-M;
    while(mx)
    {
        mx1=M;
        for(i=poz+1; i<=n; i++)
            if(l[i]==mx && v[i]>=x && v[i]<mx1)
            {
                poz=i;
                mx1=v[i];
            }
            else if(v[i]>=x && v[i]<mx1) mx1=v[i];

        g<<poz<<" ";
        x=v[poz];
        mx--;
   }

    return 0;
}