Pagini recente » Cod sursa (job #2542956) | Cod sursa (job #2044047) | Cod sursa (job #1951633) | Cod sursa (job #1582709) | Cod sursa (job #2135995)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int DIM = 100005;
int N, D[DIM];
pair<int,int> v[DIM];
inline int get_lower_bound( int x, int st, int dr ){
while( st <= dr ){
int mid = ( st + dr ) >> 1;
if( v[mid].first <= x )
st = mid + 1;
else
dr = mid - 1;
}
return dr;
}
int main(){
fin >> N;
for( int i = 1; i <= N; i++ )
fin >> v[i].second >> v[i].first;
sort( v + 1, v + N + 1 );
for( int i = 1; i <= N; i++ ){
int pos = get_lower_bound( v[i].second, 1, i );
D[i] = max( D[pos] + v[i].first - v[i].second, D[i] );
}
fout << D[N] << "\n";
return 0;
}