Pagini recente » Cod sursa (job #2838261) | Cod sursa (job #1150631) | Cod sursa (job #386155) | Cod sursa (job #3124690) | Cod sursa (job #2334213)
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int d[N];
struct roaceri{
int s,t;
};
bool cmp (roaceri a,roaceri b){
if(a.t<b.t)
return true;
if(a.t==b.t)
if(a.s<b.s)
return true;
return false;
}
roaceri v[N];
int n;
int cautb(int val){
int pas=0,p2=1<<20;
while(p2){
if(pas+p2<=n && v[pas+p2].t<=val)
pas+=p2;
p2/=2;
}
return pas;
}
int main()
{
FILE*fin,*fout;
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
int i;
fscanf(fin,"%d",&n);
for(i=1;i<=n;i++){
fscanf(fin,"%d%d",&v[i].s,&v[i].t);
}
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++){
int poz=cautb(v[i].s);
d[i]=max(d[i-1],d[poz]+v[i].t-v[i].s);
}
fprintf(fout,"%d",d[n]);
return 0;
}