Cod sursa(job #2100646)

Utilizator marcudanfDaniel Marcu marcudanf Data 5 ianuarie 2018 22:52:52
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define a second
#define b first


using namespace std;

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

pair <int, int> v[100005];

int n;
int64_t dp[100005], Max;

int main(){
	fin>>n;
	for(int i = 0; i < n; i++)
		fin >> v[i].a >> v[i].b;
	sort(v, v + n);
	dp[0] = v[0].b - v[0].a;
	for(int i = 1; i < n; i++){
		dp[i] = max(1LL * dp[i-1], 1LL * v[i].b - v[i].a);
		int stg = 0, dr = i - 1, sol = 0;
		while(stg <= dr){
			int mid = (stg + dr) / 2;
			if(v[i].a >= v[mid].b){
				sol = mid;
				stg = mid + 1;
			}else
				dr = mid - 1;
		}
		dp[i] = max(1LL * dp[i], 1LL * dp[sol] + v[i].b - v[i].a);
		Max = max(Max, dp[i]);
	}
	fout << Max;
	return 0;
}