Cod sursa(job #2158651)

Utilizator armandpredaPreda Armand armandpreda Data 10 martie 2018 14:51:31
Problema Secv Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int LIM = 5005;
int n, v[LIM], lg, dp[LIM], tata[LIM], dist[LIM];
int main() 
{
	int tot = 0;
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> v[i];
	for(int i = 1; i <= n; ++i)
	{
		int st = 1, dr = lg, mj;
		while(st <= dr)
		{
			mj = (st + dr)/2;
			if(v[i] > v[ dp[mj] ])
				st = mj+1;
			else
				dr = mj-1;
		}
		tata[i] = dp[st-1];
		if(st > 1)
			dist[i] += dist[ tata[i] ] + i - tata[i];
		if(lg < st)
		{
			lg = st;
			dp[lg] = i;
		}
		else
			if(v[i] < v[ dp[st] ] or (v[i] == v[ dp[st] ] and st == 1) or (v[i] == v[ dp[st] ] and dist[i] < dist[ dp[st] ]))
				dp[st] = i;
	}
	int st = dp[lg], dr = dp[lg];
	while(tata[st])
		st = tata[st];
	int dif = 0;
	sort(v + 1, v + n+1);
	for(int i = 1; i <= n; ++i)
		if(v[i] != v[i-1])
			dif++;
	if(dp[dif] == 0)
		cout << -1 << '\n';
	else
		cout << dr - st + 1 << '\n';
	return 0;
}