Pagini recente » Cod sursa (job #2104204) | Cod sursa (job #1361399) | Cod sursa (job #69886) | Cod sursa (job #3271024) | Cod sursa (job #922558)
Cod sursa(job #922558)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 100001
struct VECTOR{
int st;
int dr;
int val;
};
int N;
int B[Nmax];
VECTOR V[Nmax];
void citire(){
freopen("heavymetal.in", "r", stdin);
scanf("%d", &N);
for ( int i = 1; i <= N; i++ )
scanf("%d %d", &V[i].st, &V[i].dr),
V[i].val = V[i].dr - V[i].st;
fclose(stdin);
}
int cmp(VECTOR a, VECTOR b){
return a.dr < b.dr;
}
int cautare (int left, int right, int x ) {
int pos = 0;
while ( left <= right ) {
int mid = ( left + right ) / 2;
if ( V[mid].dr <= x )
left = mid + 1,
pos = mid;
else
right = mid - 1;
}
return pos;
}
void rezolva() {
for ( int i = 1; i <= N; ++i ) {
int x = cautare ( 1, i - 1, V[i].st );
B[i] = max( B[i - 1], B[x] + V[i].val );
}
}
void afis(){
freopen("heavymetal.out", "w", stdout);
printf("%d\n", B[N] );
fclose(stdout);
}
int main(){
citire();
sort ( V + 1, V + N + 1, cmp );
rezolva();
afis();
return 0;
}