Cod sursa(job #2477617)

Utilizator enedumitruene dumitru enedumitru Data 20 octombrie 2019 19:51:42
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("scmax.in"); ofstream g("scmax.out");
int n,cnt,v[100005],dp[100005],lg[100005],sol[100005];
int main(void)
{   f>>n;
    for(int i=1;i<=n;++i) f>>v[i];
    for(int i=1;i<=n;++i)
    {   if(v[i]>dp[cnt]) {dp[++cnt]=v[i]; lg[i]=cnt;}
        else
        {   int st=1,dr=cnt,x=cnt;
            while(st<=dr)
            {   int m=(st+dr)/2;
                if(dp[m]<v[i]) st=m+1; else {dr=m-1; x=m;}
            }
            dp[x]=v[i]; lg[i]=x;
        }
    }
    g<<cnt<<'\n';
    int m=0;
    for(int i=n;i && cnt;--i)
        if(lg[i]==cnt) {sol[++m]=v[i]; --cnt;}
    for(int i=m;i;--i) g<<sol[i]<<' ';
    g.close(); return 0;
}