Pagini recente » Cod sursa (job #1113495) | Cod sursa (job #2038409) | Cod sursa (job #2279257) | Cod sursa (job #1422780) | Cod sursa (job #2100646)
#include <iostream>
#include <fstream>
#include <algorithm>
#define a second
#define b first
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
pair <int, int> v[100005];
int n;
int64_t dp[100005], Max;
int main(){
fin>>n;
for(int i = 0; i < n; i++)
fin >> v[i].a >> v[i].b;
sort(v, v + n);
dp[0] = v[0].b - v[0].a;
for(int i = 1; i < n; i++){
dp[i] = max(1LL * dp[i-1], 1LL * v[i].b - v[i].a);
int stg = 0, dr = i - 1, sol = 0;
while(stg <= dr){
int mid = (stg + dr) / 2;
if(v[i].a >= v[mid].b){
sol = mid;
stg = mid + 1;
}else
dr = mid - 1;
}
dp[i] = max(1LL * dp[i], 1LL * dp[sol] + v[i].b - v[i].a);
Max = max(Max, dp[i]);
}
fout << Max;
return 0;
}