Cod sursa(job #1147475)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 19 martie 2014 21:16:30
Problema Subsir crescator maximal Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

const int inf = 2 * 1000 * 1000 * 1000 + 1;
const int MaxN = 100 * 1000 + 5;

int n;
int a[MaxN], v[MaxN], dp[MaxN], ls[MaxN];

int binsrc(int val) {
	int i = v[0], cnt = 1 << 16;
	for (; cnt; cnt >>= 1)
		if (i - cnt && v[i - cnt] >= val)
			i -= cnt;
	return i;
}

void write(int pos) {
	for (int i = pos; i >= 1; --i)
		if (a[i] < a[pos] && dp[i] + 1 == dp[pos]) {
			write(i);
			i = 0;
		}
	fout << a[pos] << ' ';
}

int main() {
	fin >> n;
	for (int i = 1; i <= n; ++i)
		fin >> a[i];
	
	int res = 0, ps;
	for (int i = 1; i <= n; ++i) {
		if (v[v[0]] != inf)
			v[++v[0]] = inf;
		int pos = binsrc(a[i]);
		v[pos] = a[i];
		dp[i] = pos + 1;
		if (res < dp[i]) {
			res = dp[i];
			ps = i;
		}
	}
	
	fout << res - 1 << '\n';
	for (int i = 1; i <= v[0]; ++i)
		fout << v[i] << ' ';
	fout << '\n';
	fin.close(); fout.close(); return 0;
}