Cod sursa(job #2236449)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 29 august 2018 16:59:51
Problema Subsir crescator maximal Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
//#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <algorithm>
  
using namespace std;
  
/********** TEMPLATE STARTS HERE ***********/
  
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define pb push_back
#define test int t; cin >> t; while(t--)
#define skip continue
#define stop break
#define sz(v) v.size()
#define endl '\n'
#define PI 3.1415926535897932384626433832795
#define EPS 1e-9
#define FR(i, l, r) for(int i = (l); i <= (r); i++)
#define gcd __gcd 
#define FO(i, a) for(auto & i : a)
#define debug(a) cout << #a << ": " << a << endl
#define debug1(a, l, r) FR(i, l, r) cout << a[i] << " "; cout << endl
#define SET(a, b) memset(a, b, sizeof(a));
#define refresh fflush(stdout);
  
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <long long> vl;
typedef vector <pii> vii;
typedef vector <pll> vll;
  
const int INF = 0x3f3f3f3f;
const int LINF = 0x3f3f3f3f3f3f3f3f;
  
template <typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template <typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
//template <typename T> inline void out(T x) { cout << x; }
 
/*********** TEMPLATE ENDS HERE *************/

ifstream cin("scmax.in");
ofstream cout("scmax.out");

const int N = 1e5 + 7;

int v[N];
int SCM[N];

vi ans;

main()
{
	int n;
	cin >> n;
	int mx = 0;
	for(int i = 1; i <= n; i++)
		cin >> v[i], SCM[i] = 1;
		
	for(int i = 2; i <= n; i++)
	{
		for(int j = 1; j < i; j++)
			if(v[j] < v[i])
				amax(SCM[i], SCM[j] + 1);
		amax(mx, SCM[i]);
	}
	cout << mx << '\n';
	int prev = INF;
	int t = mx + 1;
	for(int i = n; i >= 1; i--)
		if(SCM[i] == t - 1 && v[i] < prev)
			ans.pb(v[i]), t--, prev = v[i];
	for(int i = ans.size() - 1; i >= 0; i--)
		cout << ans[i] << ' ';
}