Pagini recente » Cod sursa (job #975223) | Cod sursa (job #1407910) | Cod sursa (job #700667) | Cod sursa (job #472081) | Cod sursa (job #3153851)
#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";
}