Cod sursa(job #1466541)

Utilizator greenadexIulia Harasim greenadex Data 29 iulie 2015 14:12:54
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair

using namespace std;

const string name = "heavymetal",
             in_file = name + ".in",
             out_file = name + ".out";

ifstream fin(in_file);
ofstream fout(out_file);

const int MAX = 1e5 + 1;

struct interval {
	int a, b;

	interval() {}

	interval(int a, int b) {
		this -> a = a;
		this -> b = b;
	}

	bool operator< (const interval& obj) const {
		return b < obj.b;
	}
} v[MAX];

int bs (int nr, int poz) {
	int left = 1, right = poz - 1, sol = 0;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (v[mid].b <= nr){
			left = mid + 1;
			sol = max(sol, mid);
		} else right = mid - 1;
	}
	return sol;
}

int n, dp[MAX];

int main() {
	fin >> n;
	for (int a, b, i = 1; i <= n; i++) {
		fin >> a >> b;
		v[i] = interval(a, b);
	}

	sort(v + 1, v + n + 1);

 	for (int i = 1; i <= n; i++){
		int poz = bs(v[i].a, i);
		dp[i] = max(dp[i - 1], v[i].b - v[i].a + dp[poz]);
	}

	fout << dp[n];
	return 0;
}