Pagini recente » Cod sursa (job #2744618) | Cod sursa (job #1010548) | Cod sursa (job #2108703) | Cod sursa (job #804842) | Cod sursa (job #1862874)
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct concert{
int st;
int dr;
};
concert v[100000];
int cmp(concert a, concert b){
if(a.dr<b.dr)
return 1;
else if(a.dr==b.dr && a.st<=b.st)
return 1;
return 0;
}
int best[100000];
int maxim(int a, int b){
if(a<b)
a=b;
return a;
}
int main()
{
FILE *fin, *fout;
int n,i,j,max;
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
fscanf(fin,"%d",&n);
max=0;
for(i=0;i<n;i++){
fscanf(fin,"%d%d",&v[i].st,&v[i].dr);
if(max<v[i].dr)
max=v[i].dr;
}
sort(v,v+n,cmp);
j=0;
best[0]=v[0].dr-v[0].st;
for(i=1;i<n;i++){
best[i]=best[i-1];
int rez=0;
for(int pas=1<<17;pas;pas>>=1){
if(rez+pas<i && v[rez+pas].dr<=v[i].st)
rez+=pas;
}
best[i]=maxim(best[i],best[rez]+(v[i].dr-v[i].st));
}
fprintf(fout,"%d",best[n-1]);
fclose(fin);
fclose(fout);
return 0;
}