Cod sursa(job #2121451)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 3 februarie 2018 18:10:19
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>
#include <set>

std::ifstream f("scmax.in");
std::ofstream g("scmax.out");

unsigned int n;
unsigned int v[100001];
std::vector<unsigned int> length(100001, 1);
unsigned int pos[100001];
unsigned int maxLength;
unsigned int maxLengthIndex;

struct element
{
	unsigned int index;
	unsigned int length;

	bool operator > (const element& other) const
	{
		if (this->length > other.length)
			return true;

		return false;
	}

	bool operator < (const element& other) const
	{
		if (this->length < other.length)
			return true;

		return false;
	}
};

std::set<element> lengths;

void Read()
{
	f >> n;
	
	for (int i = 1; i <= n; ++i)
	{
		f >> v[i];
	}
}

void modify(unsigned int i)
{
	unsigned int j = i + 1;
	unsigned int maxIndex = 0;
	element el = { i + 1, length[i + 1] };
	/*
	for (; j <= n; ++j)
	{
		if (v[j] > v[i] && length[j] > max)
		{
			max = length[j];
			maxIndex = j;
		}
	}*/

	if(v[i + 1] > v[i])
		lengths.insert(el);

	if (!lengths.empty())
	{
		length[i] = 1 + (lengths.rbegin())->length;
		maxIndex = lengths.rbegin()->index;
	}
	else
	{
		length[i] = 1;
		maxIndex = i;
	}

	if (length[i] > maxLength)
	{
		maxLength = length[i];
		maxLengthIndex = i;
	}

	pos[i] = maxIndex;
}

void Solve()
{
	unsigned int i;

	for (int i = n - 1; i > 0; --i)
	{
		modify(i);
	}

	g << maxLength << "\n";

	for (i = maxLengthIndex; pos[i] != 0; i = pos[i])
	{
		g << v[i] << " ";
	}

	g << v[i];

	g << "\n";
}

int main()
{
	Read();
	Solve();

	return 0;
}