Cod sursa(job #3141990)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 18 iulie 2023 10:58:07
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
static bool comp(const vector<int>& a, const vector<int>& b)
{
	return a[1] < b[1];
}

ull solve(vector<vector<int>>& v)
{
	sort(v.begin(), v.end(), comp);
	int n = v.size();
	ull dp[n];
	dp[0] = v[0][1] - v[0][0];
	
	for(int i = 1;i < n;++i)
	{
		int left = 0, right = i - 1;
		while(left <= right)
		{
			int mid = (left + right) / 2;
			if(v[i][0] >= v[mid][1])
				left = mid + 1;
			else
				right = mid - 1;
		}
		int L = v[i][1] - v[i][0];
		dp[i] = max(dp[i - 1], (ull)L);
		if(left)
			dp[i] = max(dp[i], L + dp[left - 1]);
	}
	return dp[n - 1];
}

int main() {
	freopen("heavymetal.in", "r", stdin);
	freopen("heavymetal.out", "w", stdout);
	int n;
	cin >> n;
	vector<vector<int>> v(n, vector<int>(2));
	for(int i = 0;i < n;++i)
		cin >> v[i][0] >> v[i][1];
	cout << solve(v) << "\n";
}