Cod sursa(job #2055958)

Utilizator flibiaVisanu Cristian flibia Data 3 noiembrie 2017 22:54:00
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

struct lol{
	int x, y;
};

bool cmp(lol a, lol b){
	if(a.y == b.y) return (a.x < b.x);
	return (a.y < b.y);
}

int n, dp[100100];
lol a[100100];

int bin(int pos){
	int st = 0, dr = pos - 1, mid;
	while(st <= dr){
		mid = (st + dr) / 2;
		if(a[mid].y <= a[pos].x) st = mid + 1;
		else dr = mid - 1;
	}
	return dr;
}

int main(){
	ifstream in("heavymetal.in");
	ofstream out("heavymetal.out");
	in >> n;
	for(int i = 1; i <= n; i++)
		in >> a[i].x >> a[i].y;
	sort(a + 1, a + n + 1, cmp);
	for(int i = 1; i <= n; i++)
		dp[i] = a[i].y - a[i].x + dp[bin(i)];
	out << *max_element(dp + 1, dp + n + 1);
	return 0;
}