Cod sursa(job #2911484)

Utilizator matthriscuMatt . matthriscu Data 29 iunie 2022 22:48:54
Problema Heavy metal Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100005
#define problem "heavymetal"

int main()
{
	freopen(problem ".in", "r", stdin);
	freopen(problem ".out", "w", stdout);

	int n;
	scanf("%d", &n);

	pair<int, int> v[NMAX];

	for (int i = 0; i < n; ++i)
		scanf("%d%d", &v[i].first, &v[i].second);

	sort(v, v + n, [](pair<int, int>& a, pair<int, int>& b) {
		if (a.second == b.second)
			return a.first < b.first;
		return a.second < b.second;
	});

	int dp[NMAX];

	for (int i = 0; i < n; ++i) {
		dp[i] = v[i].second - v[i].first;
		for (int j = 0; j < i; ++j)
			if (v[j].second <= v[i].first)
				dp[i] = max(dp[j] + v[i].second - v[i].first, dp[i]);
	}

	printf("%d\n", dp[n - 1]);
}