Pagini recente » Cod sursa (job #1915305) | Cod sursa (job #2095011) | Cod sursa (job #2704526) | Cod sursa (job #3139625) | Cod sursa (job #2548393)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct ura{
int in, sf;
};
ura v[100001];
int sol[100000];
bool cmp(ura a, ura b) {
if(a.sf<b.sf)
return true;
return false;
}
int main() {
FILE *fin, *fout;
int n, i, j, dur, st, mij, dr, u;
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
fscanf(fin, "%d",&n);
for(i=1;i<=n;i++)
fscanf(fin, "%d%d",&v[i].in,&v[i].sf);
sort(v+1,v+n+1,cmp);
sol[1]=v[1].sf-v[1].in;
for(i=2;i<=n;i++) {
sol[i]=sol[i-1];
dur=v[i].sf-v[i].in;
st=1;
dr=i;
u=-1;
while(st<=dr) {
mij=(st+dr)/2;
if(v[mij].sf<=v[i].in) {
st=mij+1;
u=mij;
}
else
dr=mij-1;
}
if(sol[u]+dur>sol[i])
sol[i]=sol[u]+dur;
}
fprintf(fout, "%d",sol[n]);
fclose( fin );
fclose( fout );
return 0;
}