Cod sursa(job #1069802)

Utilizator mikeshadowIon Complot mikeshadow Data 30 decembrie 2013 15:28:39
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <math.h>
#include <set>
 
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)
#define REP(i,a,b) \
	for (int i=a; i<=b; i++)
 
#define INF 10000000000001
 
using namespace std;


#ifdef ONLINE_JUDGE
#define fin cin
#define fout cout
#else
#ifdef TEST
ifstream fin ("input.txt");
ofstream fout ("output.txt");
#else 
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
#endif
#endif
 
#define MAXN 100000
#define pb push_back
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pp;

struct pos
{
	int v,l,p;
};

int n;
pos a[MAXN];

int main()
{
	fin>>n; 

	for (int i=0; i<n; i++)
	{
		fin>>a[i].v;
		a[i].l=1;
		a[i].p=i;
	}

	for (int i=0; i<n; i++)
		for (int j=0; j<i; j++)
			if (a[i].v>a[j].v && a[i].l<a[j].l+1)
			{
				a[i].l = a[j].l+1;
				a[i].p = j;
			}

	int m=0;
	int mpos=0;
	for (int i=0; i<n; i++)
		if (a[i].l > m)
		{
			m = a[i].l;
			mpos = i;
		}

	vector<int> sol;
	for (int i=0,it=mpos; i<m; i++)
	{
		sol.push_back(a[it].v);
		it = a[it].p;
	}

	fout<<m<<'\n';
	reverse(sol.begin(),sol.end());

	for (int i=0; i<m; i++)
		fout<<sol[i]<<' ';
	
	return 0;
}