Cod sursa(job #2822669)

Utilizator lolismekAlex Jerpelea lolismek Data 24 decembrie 2021 20:15:51
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
// problema pentru roackeri nespalati
#include <iostream>
#include <fstream>
#include <algorithm>

#define int long long

using namespace std;

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

struct spectacol {
	int start, end;
};

const int N = 1e5 + 1;
int dp[N];
spectacol v[N];

bool compare(spectacol a, spectacol b) {
	if (a.end != b.end) return a.end < b.end;
	return a.start < b.start;
}

signed main() {
	int n;
	fin >> n;
	for (int i = 1; i <= n; i++) fin >> v[i].start >> v[i].end;
	sort(v + 1, v + n + 1, compare);
	int rez = 0;
	for (int i = 1; i <= n; i++) {
		int st = 1, dr = i;
		while (dr - st > 1) {
			int mij = (st + dr) / 2;
			if (v[mij].end > v[i].start) dr = mij;
			else st = mij;
		}
		int j = st;
		dp[i] = max(dp[i - 1], dp[j] + v[i].end - v[i].start);
		rez = max(rez, dp[i]);
	}
	fout << rez;
	return 0;
}