Cod sursa(job #2674437)

Utilizator StefanSanStanescu Stefan StefanSan Data 19 noiembrie 2020 10:45:44
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include      <iostream>
#include      <fstream>
#include      <algorithm>

using namespace std;

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

struct spectacol {
	long long int inceput;
	long long int final;
} v[100001];

bool comp(spectacol a, spectacol b) {
	return (a.final < b.final) || (a.final == b.final && a.inceput < b.inceput);
}

int n, dis[100001], maxim[100001], solutie;

int main() {

	ios::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);
	
	in >> n;
	for (int i = 1; i <= n; i++) {
		in >> v[i].inceput >> v[i].final;
	}

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

	for (int i = 1; i <= n; i++) {
		int left = 1, right = i - 1, sol = 0; 
		while (left <= right) {
			int mid = (left + right) / 2;
			if (v[i].inceput >= v[mid].final) {
				sol = mid;
				left = mid + 1;
			}
			else {
				right = mid - 1;
			}
		}
		dis[i] = maxim[sol] + v[i].final - v[i].inceput;
		maxim[i] = max(maxim[i - 1], dis[i]);
	}
	for (int i = 1; i <= n; i++) solutie = max(solutie, maxim[i]);
	out << solutie;

    return 0;

}