Cod sursa(job #2979523)

Utilizator dobreraduDobre Radu Fabian dobreradu Data 15 februarie 2023 12:35:50
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#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 = n;
		while (st <= dr) {
			int mij = (st + dr) / 2;
			if (v[mij].end > v[i].start) dr = mij - 1;
			else st = mij + 1;
		}
		int j = dr;
		dp[i] = max(dp[i - 1], dp[j] + v[i].end - v[i].start);
		rez = max(rez, dp[i]);
	}
	fout << rez;
	return 0;
}