Cod sursa(job #794544)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
#define nmax 100005
#define ll long long
int n, a[nmax], dp[nmax], Poz[nmax];
void citeste(){
f >> n;
for(int i=1; i<=n; ++i) f >> a[i];
}
void cauta(int val, int i){
int st = 0;
int dr = dp[0] + 1;
while(dr - st > 1){
int mij = (st + dr) / 2;
if (dp[mij] >= val){
dr = mij;
}else st = mij;
}
if (dr == dp[0] + 1){//daca trebuie adaugat elementul
dp[0]++;
dp[ dp[0] ] = val;
Poz[ dp[0] ] = i;
}else {
dp[ dr ] = val;
Poz[ dr ] = i;
}
}
void fa_drum(int lung, int i){
for(; Poz[lung] != i; --i);//cat timp nu am intalnit pozitia din a[] a elementului din dp[] de pe pozita lung
if (lung > 1) fa_drum(lung-1, i);
g << a[i] << " ";
}
void rezolva(){
//ideea ar fi cam asa : fac un dp[i] = x, unde x e cel mai mic element posibil al unui subsir crescator maximal de lungime i
//si mai tin minte pozitia in a[] a unui element din dp
for(int i=1; i<=n; ++i){
cauta(a[i], i);
}
g << dp[0] << "\n";
fa_drum(dp[0], n);
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}