Pagini recente » Cod sursa (job #553204) | Cod sursa (job #1125177) | Cod sursa (job #3158383) | Cod sursa (job #1375384) | Cod sursa (job #2333609)
#include <fstream>
#include <algorithm>
#include <iostream>
#define NMAX 100000
using namespace std;
ifstream fin ( "heavymetal.in" );
ofstream fout ( "heavymetal.out" );
pair < int, int > A[1 + NMAX];
int n, ans, D[1 + NMAX];
int bs ( int val, int dr );
int main() {
fin >> n;
for ( int i = 1; i <= n; ++i )
fin >> A[i].second >> A[i].first;
sort ( A + 1, A + 1 + n );
for ( int i = 1; i <= n; ++i ) {
D[i] = A[i].first - A[i].second;
D[i] = max ( D[i] + D[bs ( A[i].second, i - 1 )], D[i - 1] );
ans = max ( ans, D[i] );
}
fout << ans;
}
int bs ( int val, int dr ) {
int st = 1, mid, ans = 0;
while ( st <= dr ) {
mid = ( st + dr ) / 2;
if ( A[mid].first > val )
dr = mid - 1;
else {
ans = mid;
st = mid + 1;
}
}
return ans;
}