Pagini recente » Cod sursa (job #409400) | Cod sursa (job #1497726) | Cod sursa (job #2775066) | Cod sursa (job #522852) | Cod sursa (job #1862883)
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct concert{
int st;
int dr;
};
concert v[100001];
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[100001];
int maxim(int a, int b){
if(a<b)
a=b;
return a;
}
int main()
{
FILE *fin, *fout;
int n,i,max;
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
fscanf(fin,"%d",&n);
max=0;
for(i=1;i<=n;i++){
fscanf(fin,"%d%d",&v[i].st,&v[i].dr);
if(max<v[i].dr)
max=v[i].dr;
}
sort(v+1,v+n+1,cmp);
best[0]=0;
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]);
fclose(fin);
fclose(fout);
return 0;
}