Pagini recente » Cod sursa (job #2689758) | Cod sursa (job #493778) | Cod sursa (job #429391) | Cod sursa (job #347210) | Cod sursa (job #515385)
Cod sursa(job #515385)
#include<stdio.h>
#include<algorithm>
using namespace std;
FILE*f=fopen("heavymetal.in","r");
FILE*g=fopen("heavymetal.out","w");
int N,i,p,u,m,S[100005];
struct interv{
int a;
int b;
}W[100005];
int cmp(interv a,interv b){
if ( a.b != b.b )
return a.b < b.b;
return a.a < b.a;
}
int main () {
fscanf(f,"%d",&N);
for ( i = 1 ; i <= N ; ++i )
fscanf(f,"%d %d",&W[i].a,&W[i].b);
sort(W+1,W+N+1,cmp);
for ( i = 1 ; i <= N ; ++i ){
p = 0 ; u = i - 1;
while ( p <= u ){
m = p + (u - p) / 2;
if ( W[m].b > W[i].a )
u = m - 1;
else
p = m + 1;
}
if ( W[i].b - W[i]. a + S[ u ] > S[i-1] )
S[i] = W[i].b - W[i]. a + S[ u ];
else
S[i] = S[i-1];
}
fprintf(g,"%d\n",S[N]);
fclose(f);
fclose(g);
return 0;
}