Cod sursa(job #3259217)

Utilizator MilitaruMihaiMihaiMIlitaru MilitaruMihai Data 25 noiembrie 2024 16:07:58
Problema Subsir 2 Scor 36
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int n,mx,mn[5005],a[5005],k,l[5005];
void drum(int k){
    for (int j=k;j>=1 && mx>0;j--){
        if (l[j]==mx && a[j]<=a[k])
        {
            mx--;
            drum(k);
            fout<<j<<' ';
        }
    }
}
int main()
{
    fin>>n;
    mx=0;
    mn[0]=-1000005;
    for (int i=1;i<=n;i++){
        fin>>a[i];
        if (a[i]>=mn[mx]) mn[++mx]=a[i],k=i,l[i]=mx;
        else {
            int st=1,dr=mx,sol=0;
            while (st<=dr){
                int mij=(st+dr)/2;
                if (mn[mij]<a[i]) sol=mij,st=mij+1;
                    else dr=mij-1;
            }
            l[i]=sol+1;
            mn[sol+1]=max(mn[sol+1],a[i]);
        }
    }
    fout<<mx<<'\n';
    drum(k);
    return 0;
}