Pagini recente » Cod sursa (job #188655) | Cod sursa (job #2106713) | Cod sursa (job #974861) | Cod sursa (job #866660) | Cod sursa (job #2055959)
#include <bits/stdc++.h>
using namespace std;
struct lol{
int x, y;
};
bool cmp(lol a, lol b){
if(a.y == b.y) return (a.x < b.x);
return (a.y < b.y);
}
int n, dp[100100];
lol a[100100];
int bin(int pos){
int st = 0, dr = pos - 1, mid;
while(st <= dr){
mid = (st + dr) / 2;
if(a[mid].y <= a[pos].x) st = mid + 1;
else dr = mid - 1;
}
return dr;
}
int main(){
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
in >> n;
for(int i = 1; i <= n; i++)
in >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i++)
dp[i] = max(a[i].y - a[i].x + dp[bin(i)], dp[i-1]);
out << dp[n];
return 0;
}