Pagini recente » Cod sursa (job #2989693) | Cod sursa (job #1432504) | Cod sursa (job #2723091) | Cod sursa (job #1070928) | Cod sursa (job #2541520)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int dp[5 + N];
int Max[5 + N];
pair <int,int> spec[5 + N];
bool cmp(pair <int,int> a, pair <int,int> b){
return a.second < b.second;
}
int cautbin(int n, int dr){
int r, pas;
r = 0;
pas = 1 << 20;
while(pas){
if(r + pas <= n && spec[r + pas].second <= dr)
r += pas;
pas >>= 1;
}
return r;
}
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d%d", &spec[i].first, &spec[i].second);
sort(spec + 1, spec + n + 1, cmp);
for(int i = 1; i <= n; i++){
int st, dr, pos;
st = spec[i].first;
dr = spec[i].second;
pos = cautbin(i, st);
dp[i] = dr - st + Max[pos];
Max[i] = max(Max[i - 1], dp[i]);
}
printf("%d\n", Max[n]);
return 0;
}