Pagini recente » Cod sursa (job #1740226) | Cod sursa (job #2472286) | Cod sursa (job #624520) | Cod sursa (job #560054) | Cod sursa (job #2719384)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct data{
int x, y;
}v[NMAX];
inline bool cmp(data a, data b){
if(a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
int dp[NMAX];
int main()
{
int n;
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
for(int i = 1; i <= n; ++i){
int st = 1;
int dr = i - 1;
int best = 0;
while(st <= dr){
int mij = (st + dr) / 2;
if(v[mij].y <= v[i].x){
best = mij;
st = mij + 1;
}
else dr = mij - 1;
}
dp[i] = max(dp[i - 1], dp[best] + v[i].y - v[i].x);
}
fout << dp[n] << '\n';
return 0;
}