Pagini recente » Cod sursa (job #2689669) | Cod sursa (job #2903473) | Cod sursa (job #2628446) | Cod sursa (job #527143) | Cod sursa (job #1883082)
#include <bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
#define MAX 100001
#define fi first
#define se second
int N;
pair <int, int> ab[MAX];
int dp[MAX];
inline int caut(int val) {
int pas = 1 << 22;
int r = 0;
while(pas) {
if(r + pas <= N && ab[r + pas].se <= val)
r += pas;
pas >>= 1;
}
return r;
}
bool cmp(pair <int, int>a, pair <int, int>b) {
return a.se < b.se;
}
int main() {
f >> N;
for(int i = 1;i <= N;i++)
f >> ab[i].fi >> ab[i].se;
sort(ab + 1, ab + N + 1, cmp);
for(int i = 1;i <= N;i++) {
int ct = caut(ab[i].fi);
dp[i] = max(dp[i - 1], dp[ct] + (ab[i].se - ab[i].fi));
}
g << dp[N];
f.close(), g.close();
return 0;
}