Cod sursa(job #3182580)

Utilizator radu1331Mocan Radu radu1331 Data 9 decembrie 2023 10:39:30
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

using namespace std;

#define fastIO ios_base::sync_with_stdio(NULL);cin.tie(NULL)
#define testCases int tc;cin>>tc;while(tc--)
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(),(a).end()
#define PI 3.1415926535897932384626433832795l

const int NMAX = 1e5 + 5;

template<typename T> inline T gcd(T a, T b) {return (b?__gcd(a, b):a);}
template<typename T> inline T lcm(T a, T b) {return (a*(b/gcd(a, b)));}

static inline void solve();

void print ( int x, int* last, int* a )
{
    if ( a [ x ] == 0 ) return;
    cout << a [ x ] << ' '; 
    print ( last [ x ], last, a );
}

int main ( int argc, char** argv )
{

    ( void )! freopen ( "scmax.in" , "r" , stdin );
    ( void )! freopen ( "scmax.out" , "w" , stdout );

    fastIO;

    solve();

    return 0;
}

static inline void solve()
{
    // exemplu de dp
    // int dp [ 3 ];
    // dp [ 0 ] = 1, dp [ 1 ] = 2;
    // int n; cin >> n;
    // int i = 1;
    // while ( i < n )
    // {
    //     dp [ ( i + 1 ) % 3 ] = dp [ i % 3 ] + dp [ ( i - 1 ) % 3 ];
    //     i ++;
    // }
    // cout << dp [ ( i - 1 ) % 3 ];
    // 
    int n; cin >> n;
    int a [ NMAX ], best [ NMAX ], last [ NMAX ];

    best [ 1 ] = 1; 

    for ( int i = 1; i <= n; ++ i )
        cin >> a [ i ];
    for ( int i = n; i >= 1; -- i )
    {
        int min = 0;
        for ( int j = i + 1; j <= n; ++ j )
        {
            if ( a [ i ] < a [ j ] && best [ j ] > min ) min = best [ j ], last [ i ] = j;
        }
        best [ i ] = 1 + min;
    }


    int max = 0, prev = 0;
    for ( int i = 1; i <= n; ++ i )
    {
        if ( best [ i ] > max ) max = best [ i ], prev = i;
    }

    cout << max << '\n';
    print ( prev, last, a );
}