Pagini recente » Cod sursa (job #52326) | Cod sursa (job #1848300) | Cod sursa (job #2345882) | Cod sursa (job #722173) | Cod sursa (job #2546800)
#include <fstream>
#include <algorithm>
using namespace std;
int const NM = 1e5 + 1;
pair <int , int> v [NM] ;
int ans [NM] , dp [NM];
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
bool crt (pair <int , int> a , pair <int , int> b){
return a . second < b . second;
}
int main (){
int n;
f >> n;
for(int i = 1 ; i <= n ; ++ i)
f >> v [i] . first >> v [i] . second;
sort (v + 1 , v + 1 + n , crt);
for(int i = 1 ; i <= n ; ++ i){
int from , to;
from = v [i] . first;
to = v [i] . second;
int pas = (1 << 16) , found = 0;
while (pas){
if (pas + found <= i && v [pas + found] . second <= from)
found += pas;
pas >>= 1;
}
dp [i] = to - from + ans [found];
ans [i] = max (ans [i - 1] , dp [i]);
}
g << ans [n];
return 0;
}