Cod sursa(job #2757356)

Utilizator DauCuDalta43Diaconu Razvan DauCuDalta43 Data 5 iunie 2021 09:41:04
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int a[100005],P[100005],n,sol[100005];
int dp[100005],k;

void CautBin(int i)
{
    int st,dr,p,mij,x=a[i];
    if(x<=dp[1])
    {
        dp[1]=x;
        P[i]=1;
        return;
    }
    if(x>dp[k])
    {
        k++;
        dp[k]=x;
        P[i]=k;
        return;
    }
    st=1;dr=k;p=k;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(x<=dp[mij])
        {
            p=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    dp[p]=x;
    P[i]=p;
}

int main()
{
    int i,len,ult;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    dp[1]=a[1];
    P[1]=1;
    k=1;
    for(i=2;i<=n;i++)
        CautBin(i);
    fout<<k<<"\n";
    ult=2000000001;
    for(len=k,i=n;i>=1&&len>0;i--)
        if(P[i]==len&&a[i]<ult)
        {
            ult=a[i];
            sol[len]=a[i];
            len--;
        }
    for(i=1;i<=k;i++)
        fout<<sol[i]<<" ";
    return 0;
}