Cod sursa(job #3153851)

Utilizator moldovan_robert_lolMoldovan Robert moldovan_robert_lol Data 1 octombrie 2023 16:35:58
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

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

int x;
std::vector<std::pair<int,int>> arr;
int64_t dp[100005];
int64_t dp_max[100005];

int main() {
	fin >> x;
	arr.resize(x);
	for (auto& i : arr) {
		fin >> i.first >> i.second;
	}

	std::sort(arr.begin(),arr.end());
	arr.emplace_back(1000000005,1000000005);

	const auto ub = [&](int val) {
		int ret = x;
		int l = 0, r = x-1;
		while (l<=r) {
			int m = (l+r)>>1;
			if (arr[m].first>=val) {
				ret = m;
				r = m-1;
			}
			else {
				l = m+1;
			}
		}

		return ret;
	};

	dp[x] = dp_max[x] = 0;
	for (int i = x-1; i >= 0; i--) {
		dp[i] = arr[i].second - arr[i].first + dp_max[ub(arr[i].second)];
		dp_max[i] = std::max(dp_max[i+1],dp[i]);
	}

	fout << dp_max[0] << "\n";
}