Pagini recente » Cod sursa (job #1269256) | Cod sursa (job #1821635) | Cod sursa (job #2692244) | Cod sursa (job #1515997) | Cod sursa (job #1882472)
#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;
}
int main() {
f >> N;
for(int i = 1;i <= N;i++)
f >> ab[i].fi >> ab[i].se;
sort(ab + 1, ab + N + 1);
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;
}