Pagini recente » Cod sursa (job #2957123) | Cod sursa (job #2706488) | Cod sursa (job #2399289) | Cod sursa (job #1080530) | Cod sursa (job #2729763)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMAX = 1e5 + 5;
struct interval {
int x, y;
} a[NMAX];
bool fcmp(interval A, interval B) {
if (A.y != B.y)
return A.y < B.y;
return A.x < B.x;
}
int dp[NMAX];
void solve() {
int N;
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> a[i].x >> a[i].y;
sort (a + 1, a + N + 1, fcmp);
for (int i = 1; i <= N; ++i) {
int st = 1, dr = i - 1, best = 0;
while (st <= dr) {
int mid = (st + dr) >> 1;
if (a[mid].y <= a[i].x) {
best = mid;
st = mid + 1;
} else {
dr = mid - 1;
}
}
dp[i] = max(dp[i - 1], dp[best] + a[i].y - a[i].x);
}
fout << dp[N] << '\n';
}
void close_files() {
fin.close();
fout.close();
}
int main() {
solve();
close_files();
return 0;
}