Pagini recente » Cod sursa (job #1597411) | Cod sursa (job #493217) | Cod sursa (job #132998) | Cod sursa (job #2124245) | Cod sursa (job #2136520)
//Pt emma
#include <iostream>
#include <fstream>
#include <algorithm>
#define DIM 100002
#define pr pair<int, int>
#define f first
#define s second
using namespace std;
ifstream in ("heavymetal.in");
ofstream out("heavymetal.out");
int n, dp[DIM];
pr ev[DIM];
bool cmp(pr a, pr b){
return a.s < b.s;
}
int main() {
in>>n;
for(int i = 1; i <= n; ++ i)
in>>ev[i].f>>ev[i].s;
sort(ev + 1, ev + n + 1, cmp);
for(int i = 1; i <= n; ++ i){
int st = 1;
int dr = i - 1;
while(st <= dr){
int mid = (st + dr) / 2;
if(ev[mid].s <= ev[i].f)
st = mid + 1;
else
dr = mid - 1;
}
dp[i] = dp[dr] + ev[i].s - ev[i].f;
}
int maxim = -1;
for(int i = 1; i <= n; ++ i)
maxim = max(maxim, dp[i]);
out<<maxim;
return 0;
}