Pagini recente » Cod sursa (job #163156) | Cod sursa (job #599932) | Cod sursa (job #1205283) | Cod sursa (job #1692762) | Cod sursa (job #1862288)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct prb {int st,dr,timp;};
prb d[100001],v[100001];
bool cmp (prb a, prb b)
{
return a.dr<b.dr;
}
int main()
{
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
int i,n,st,dr,mij,pp;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>v[i].st>>v[i].dr;
v[i].timp=v[i].dr-v[i].st;
}
sort(v+1,v+n+1,cmp);
d[1].st=v[1].st;
d[1].dr=v[1].dr;
d[1].timp=v[1].timp;
for(i=2;i<=n;i++)
{
if(v[i].st<d[i-1].dr)
{
st=0;
dr=i-2;
while(st<=dr)
{
mij=(st+dr)/2;
if(d[mij].dr<=v[i].st)
{
pp=0;
st=mij+1;
}
else
{
pp=1;
dr=mij-1;
}
}
if(pp==1)
mij--;
if(d[mij].timp+v[i].timp>d[i-1].timp)
{
d[i].st=d[i-1].st;
d[i].dr=v[i].dr;
d[i].timp=v[i].timp+d[mij].timp;
}
else
{
d[i].st=d[i-1].st;
d[i].dr=d[i-1].dr;
d[i].timp=d[i-1].timp;
}
}
else
{
d[i].st=d[i-1].st;
d[i].dr=v[i].dr;
d[i].timp=d[i-1].timp+v[i].timp;
}
}
fout<<d[n].timp;
return 0;
}