Pagini recente » Cod sursa (job #592232) | Cod sursa (job #1512518) | Cod sursa (job #2715907) | Cod sursa (job #2114537) | Cod sursa (job #1093726)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n,i,j,Max=-1,timp[100001],p,u,mij;
struct str{
int inc,sf;
}v[100001];
int cmp(str x,str y){
return x.sf<y.sf;
}
int main(){
f>>n;
for(i=1;i<=n;i++)
f>>v[i].inc>>v[i].sf;
sort(v+1,v+n+1,cmp);
timp[1]=v[1].sf-v[1].inc;
Max=timp[1];
for(i=2;i<=n;i++)
{
p=1;
u=i;
timp[i]=max(timp[i-1],v[i].sf-v[i].inc);
while(p<=u)
{
mij=(p+u)/2;
if(v[i].inc>=v[mij].sf){
timp[i]=max(timp[i],v[i].sf-v[i].inc+timp[mij]);
p=mij+1;
}
else
u=mij-1;
}
if(Max<timp[i])
Max=timp[i];
}
g<<Max;
return 0;
}