Pagini recente » Cod sursa (job #1162217) | Cod sursa (job #1819374) | Cod sursa (job #2912399) | Cod sursa (job #1589224) | Cod sursa (job #2894526)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
long long n, dp[100005];
struct elem
{
long long val1, val2;
}v[100005];
inline bool cmp(const elem a, const elem b)
{
return a.val2 < b.val2;
}
int main()
{
fin >> n;
for (long long i = 1; i <= n; i++) {
fin >> v[i].val1 >> v[i].val2;
}
sort(v + 1, v + n + 1, cmp);
for (long long i = 1; i <= n; i++) {
long long st = 1, dr = i - 1, poz = 0;
while (st <= dr) {
long long mijl = (st + dr) / 2;
if (v[i].val1 >= v[mijl].val2) {
st = mijl + 1;
poz = mijl;
} else {
dr = mijl - 1;
}
}
dp[i] = max(dp[i - 1], dp[poz] + v[i].val2 - v[i].val1);
}
fout << dp[n];
return 0;
}