Cod sursa(job #2479693)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 24 octombrie 2019 11:22:25
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>

using namespace std;

ifstream cin("scmax.in");
ofstream cout("scmax.out");

const int L = 16;
long long b,v[100005],n,k,d[100005],indi,maxi,a[100005];

int caut(int x,int a)
{
    int pas=1<<L;
    int r=0;
    while (pas!=0){
        if(r+pas<a && v[r+pas]<=x)
            r+=pas;
        pas/=2;
    }
    return r;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
        b=caut(v[i],i);
        if(b){
            if(v[i]==v[b]){
                d[i]--;
            }
            d[i]+=d[b]+1;
        }
        else{
            d[i]=1;
        }
        if(d[i]>maxi){
            maxi=d[i];
            indi=i;
        }
    }
    cout<<maxi<<'\n';
    long long maxi1=maxi;
    a[maxi]=v[indi];
    for(int i=indi-1;i>=0;i--){
        if(v[i]<v[indi] && d[i]==maxi-1){
            indi=i;
            maxi--;
            a[maxi]=v[i];
        }
    }
    for(int i=1;i<=maxi1;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}