Pagini recente » Cod sursa (job #626821) | Cod sursa (job #2878140) | Cod sursa (job #858137) | Cod sursa (job #1824994) | Cod sursa (job #2346066)
#include <bits/stdc++.h>
std::istream& operator >> (std::istream& stream, std::pair <int, int>& data) {
return stream >> data.first >> data.second;
}
bool cmp(const std::pair <int, int>& pair, const std::pair <int, int>& other) {
if (pair.second == other.second)
return pair.first < other.first;
return pair.second < other.second;
}
#define int_pair std::pair <int, int>
#define MAXN 100005
int N, DP[MAXN];
int_pair V[MAXN];
std::ifstream In ("heavymetal.in");
std::ofstream Out("heavymetal.out");
void Citire() {
In >> N;
for (int i=1; i<=N; ++i)
In >> V[i];
}
void Rezolvare() {
std::sort(V+1, V+N+1, cmp);
for (int i=1, lbound, rbound, mid, ans; i<=N; ++i) {
DP[i] = std::max(DP[i-1], V[i].second - V[i].first);
lbound = 1, rbound = i-1, ans = 0;
while (lbound <= rbound) {
mid = (lbound + rbound)/2;
if (V[mid].second <= V[i].first)
ans = mid, lbound = mid+1;
else
rbound = mid-1;
}
if (ans)
DP[i] = std::max(DP[i], DP[ans] + V[i].second - V[i].first);
} Out << DP[N] << '\n';
}
int main()
{
Citire();
Rezolvare();
return 0;
}