Pagini recente » Cod sursa (job #1177462) | Cod sursa (job #1720128) | Cod sursa (job #742196) | Cod sursa (job #2765087) | Cod sursa (job #2055958)
#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] = a[i].y - a[i].x + dp[bin(i)];
out << *max_element(dp + 1, dp + n + 1);
return 0;
}