Pagini recente » Cod sursa (job #496546) | Cod sursa (job #2046790) | Cod sursa (job #1078733) | Cod sursa (job #1635211) | Cod sursa (job #2540544)
#include<fstream>
#include<algorithm>
#define nmax 100007
using namespace std;
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
struct ana
{
int x,y;
}v[nmax];
bool cmp(ana a,ana b)
{
if(a.y!=b.y)
return a.y<b.y;
return a.x<b.x;
}
int sol[nmax],n,i,jm,st,dr,mij,rezultat;
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
sol[1]=v[1].y-v[1].x;
for(i=2;i<=n;i++)
{
sol[i]=sol[i-1]; /// nu il pun
st=1,dr=i-1;
rezultat=0;
mij=(st+dr)/2;
while(st<=dr)
{
if(v[mij].y<=v[i].x)
{
rezultat=mij;
st=mij+1;
}
else
dr=mij-1;
mij=(st+dr)/2;
}
sol[i]=max(sol[i-1],sol[mij]+v[i].y-v[i].x);
}
g<<sol[n];
}