Pagini recente » Cod sursa (job #2030201) | Cod sursa (job #2083242) | Cod sursa (job #1696731) | Cod sursa (job #448684) | Cod sursa (job #2038451)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct pereche{
int start;
int stop;
int timp;
}trupe[100001];
bool cmp(pereche a, pereche b){
if(b.stop>a.stop)
return 1;
if(b.stop==a.stop && b.start>a.start)
return 1;
return 0;
}
int cauta(int li, int ls, int val){
if(ls==0)
return 0;
int mij;
while(li<=ls){
mij=(li+ls)/2;
if(trupe[mij].stop==val)
return mij;
else if(trupe[mij].stop<val)
li=mij+1;
else
ls=mij-1;
}
return ls;
}
int main()
{
FILE *fin, *fout;
int n,a,b,i,time,x;
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
fscanf(fin,"%d",&n);
for(i=1;i<=n;i++){
fscanf(fin,"%d %d\n",&a,&b);
trupe[i].start=a;
trupe[i].stop=b;
}
sort(trupe,trupe+n+1,cmp);
time=0;
for(i=1;i<=n;i++){
x=cauta(1,i-1,trupe[i].start);
trupe[i].timp=trupe[x].timp+(trupe[i].stop-trupe[i].start);
time=time>trupe[i].timp?time:trupe[i].timp;
}
fprintf(fout,"%d\n",time);
fclose(fin);
fclose(fout);
return 0;
}