Cod sursa(job #2647723)

Utilizator MarcGrecMarc Grec MarcGrec Data 5 septembrie 2020 23:34:42
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb
#define MAX_N 100000

#include <fstream>
#include <algorithm>
using namespace std;

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

struct DINT64
{
	int64_t x, y;
	
	bool operator< (const DINT64& other) const
	{
		if (x != other.x)
		{
			return x < other.x;
		}
		
		return y < other.y;
	}
};

int n;
int64_t Dp[MAX_N + 2];
DINT64 I[MAX_N + 1];

int Bs(int lb);

int main()
{
	fin >> n;
	
	for (int i = 1; i <= n; ++i)
	{
		fin >> I[i].x >> I[i].y;
	}
	
	sort(I + 1, I + n + 1);
	
	int64_t res = 0;
	
	for (int i = n; i >= 1; --i)
	{
		int index = Bs(i);
		
		Dp[i] = max(Dp[i + 1], I[i].y - I[i].x + Dp[index]);
		
		if (res < Dp[i])
		{
			res = Dp[i];
		}
	}
	
	fout << res;
	
	fin.close();
	fout.close();
	return 0;
}

int Bs(int index)
{
	int l = 1, r = n, mid, res = 0;
	
	while (l <= r)
	{
		mid = (l + r) / 2;
		
		if (I[mid].x < I[index].y)
		{
			l = mid + 1;
		}
		else
		{
			res = mid;
			r = mid - 1;
		}
	}
	
	return res;
}