Cod sursa(job #1751821)

Utilizator MickeyTurcu Gabriel Mickey Data 1 septembrie 2016 23:39:33
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<fstream>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<array>
#include<deque>
#include<unordered_set>
#include<set>
#include<math.h>
using namespace std;
int n, dp[100100], i, a, b, val,el,prvval,j,anteval,ok,max1;
vector<pair<int, int>>v[100010];
vector<pair<int, int>>::iterator it;
int main()
{
	ifstream f("heavymetal.in");
	ofstream g("heavymetal.out");
	f >> n;
	for (i = 1; i <= n; i++)
	{
		f >> a >> b;
		v[i].push_back(make_pair(a, b));
	}
	sort(v + 1, v + n + 1);
	max1 = -1;
	for (j = 1; j <= n; j++)
	{
		i = v[j].begin()->first;
		ok = 0;
		if (i != v[j].begin()->second)
		{
			if (dp[i] == 0)
				dp[i] = prvval;
			else
			{
				dp[i] = max(prvval, dp[i]);
			}
			i++;
		}
		while (i != v[j].begin()->second)
		{
			if (dp[i] == 0)
				dp[i] = prvval;
			else
			{
				dp[i] = max(anteval, dp[i]);
				ok = 1;
			}
			i++;
		}
		if(!ok)
			dp[i] =  v[j].begin()->second - v[j].begin()->first+prvval;
		else
			dp[i] = v[j].begin()->second - v[j].begin()->first + anteval;
		if (max1 < dp[i])
			max1 = dp[i];
		el = anteval;
		anteval = prvval;
		if (!ok)
			prvval = prvval + v[j].begin()->second - v[j].begin()->first;
		else
			prvval = el + v[j].begin()->second - v[j].begin()->first;
	}
	g << max1;
	return 0;
}