Cod sursa(job #2672457)

Utilizator Danut200333Dumitru Daniel Danut200333 Data 13 noiembrie 2020 23:47:10
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>

using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
long long n,i,a[5101],l[5101],j,max1,k,poz,min1,x;
int main()
{
    fin>>n;
    for(i=1; i<=n; i++)fin>>a[i];
    for(i=n; i>=1; i--)
    {
        for(j=i+1,min1=100000000; j<=n; j++)
            if(a[j]>=a[i]&&a[j]<min1)
            {
                min1=min(min1,a[j]);
                l[i]=min(l[i],l[j]+1);
                if(!l[i])l[i]=l[j]+1;
            }
        if(l[i]==0)l[i]=1;
    }
    for(i=1,min1=100000000,max1=100000000; i<=n; i++)
    {
        if(a[i]<min1)
        {
            min1=a[i];
            max1=min(max1,l[i]);
        }
    }
    fout<<max1<<'\n';
    x=-100000000;
    for(k=max1; k>=1; k--)
    {
        min1=100000000;
        max1=100000000;
        for(i=poz+1; i<=n; i++)
        {
            if(l[i]==k&&a[i]>=x&&a[i]<min1)
            {
                poz=i;
                min1=a[i];
            }
            else if(a[i]>=x&&a[i]<min1)min1=a[i];
        }
        fout<<poz<<" ";
        x=a[poz];
    }
    return 0;
}