Cod sursa(job #2647122)

Utilizator KillHorizon23Orban Robert KillHorizon23 Data 3 septembrie 2020 11:58:51
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
typedef long long ll;
typedef pair<int, int> peir;
#define x first
#define y second
const int NMAX = 100002;
vector<peir> v(NMAX);
vector<int> mx(NMAX), D(NMAX);
inline bool comp(peir a, peir b)
{
	if (a.y == b.y) return a.x < b.x;
	return a.y < b.y;
}
int main()
{
	ios::sync_with_stdio(false);
	fin.tie(0);

	int n;
	fin >> n;

	for (int i = 1; i <= n; ++i)
		fin >> v[i].x >> v[i].y;
	sort(v.begin() + 1, v.begin() + n + 1, comp);

	for (int i = 1; i <= n; ++i)
	{
		int s = 1, d = i- 1, mj, rez = 0;
		while (s <= d)
		{
			mj = s + (d - s) / 2;
			if (v[i].x >= v[mj].y)
				rez = mj, s = mj + 1;
			else d = mj - 1;
		}
		D[i] = v[i].y - v[i].x + mx[rez], mx[i] = max(mx[i - 1], D[i]);
	}
	
	int rez = 0;
	for (int i = 1; i <= n; ++i) rez = max(rez, mx[i]);
	fout << rez;
	
	return 0;
}