Cod sursa(job #2835484)

Utilizator PatrickvasileSoltan Cristian Patrickvasile Data 18 ianuarie 2022 19:48:19
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>
#define fri(a, b) for (int i = (a); i < (b); ++i)
#define frj(a, b) for(int j = a; j < b; j++)
#define frk(a, b) for(int k = a; k < b; k++)
#define frm(a, b, i) for(int i = b; i >= a; i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz size()
#define rall(x) x.rbegin(), x.rend()
#define ct(x) cout << x
#define cts(x) cout << x << ' '
#define ctn(x) cout << x << '\n'
#define Y cout << "YES" << '\n'
#define N cout << "NO" << '\n'
using namespace std;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vs = vector<string>;
using ml = map<ll, ll>;
template <typename T>void read(T n, vector<T> &a){fri(0, n){cin >> a[i];}}
template<typename T> void print(T n, vector<T> &a){fri(0, n){cts(a[i]);}}
string __fname = "scmax"; ifstream in (__fname + ".in"); ofstream out (__fname + ".out"); 
#define cin in 
#define cout out
 

const int mx = 1000001;
ll dp[100000] = {0};
int a[100000];
ll pos[100000] = {-1};


void solve(){
    ll n;
    cin >> n;
    fri(0, n){
        cin >> a[i];
    }
    int m = -1, loc = 0;
    fri(0, n){
        for(int j = i -1; j >= 0; j--){
            if(a[i] > a[j] && dp[i] < dp[j] + 1){
                dp[i] = dp[j] + 1;
                pos[i] = j;
                if(m < dp[i]){
                    m = dp[i];
                    loc = i;
                }
            }
        }
    }
    ctn(m + 1);
    vl rs;
    rs.pb(a[loc]);
    while(m--){
        rs.pb(a[pos[loc]]);
        loc = pos[loc];
    }
    reverse(all(rs));
    fri(0, rs.sz){
        cts(rs[i]);
    }
    ct('\n');
}

 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    // int t;
    // cin >> t;
    // while(t--)
        solve();
}