Pagini recente » Cod sursa (job #2738103) | Cod sursa (job #2134343) | Cod sursa (job #2480141) | Cod sursa (job #2671872) | Cod sursa (job #1950770)
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 100100;
int noConcerts ;
struct SHOW {
int st , en ;
};
SHOW conc[ N ] ;
int bestSol [ N ];
bool cmp ( SHOW a , SHOW b ){
return a.en < b.en ;
}
int bnrSrch ( int val , int dr ){
static int st , mid , sol ;
st = 0 ;
while ( st <= dr ){
mid = ( st + dr ) / 2 ;
if ( conc[ mid ].en > val ){
dr = mid - 1 ;
}else if ( conc[ mid ].en <= val ){
sol = mid ;
st = mid + 1;
}
}
return sol ;
}
int main(){
int i ;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&noConcerts );
for ( i = 1 ; i <= noConcerts ; i++ ){
scanf("%d%d",&conc[ i ].st ,&conc [ i ].en );
}
sort ( conc + 1 , conc + noConcerts + 1 , cmp );
for ( i = 1 ; i <= noConcerts ; i ++ ){
bestSol [ i ] = bestSol [ i - 1 ];
int firstBehind = bnrSrch ( conc[ i ].st , i - 1 );
bestSol [ i ] = max ( bestSol [ i ] , bestSol [ firstBehind ] + conc[ i ].en - conc [ i ].st );
}
printf("%d",bestSol [ noConcerts ] );
return 0;
}