Pagini recente » Cod sursa (job #1578329) | Cod sursa (job #2159113) | Cod sursa (job #2020622) | Cod sursa (job #2976975) | Cod sursa (job #2587954)
///SLIPKNOT PSYCHOSOCIAL
//the best band and the best song
#include<fstream>
#include<algorithm>
using namespace std;
ifstream heavy("heavymetal.in");
ofstream metal("heavymetal.out");
struct elem
{
int x,y,heavymetal;
};
elem v[100002];
inline bool cmp(const elem &a,const elem &b)
{
return a.y<b.y;
}
int n,w[200002],slipknot[200002];
int SLIPKNOT(int x)
{
int st=1,dr=2*n,mij;
while(st<=dr)
{
mij=(st+dr)/2;
if(x<=w[mij])
dr=mij-1;
else
st=mij+1;
}
return dr+1;
}
int main()
{
int i,k=1;
heavy>>n;
for(i=1;i<=n;i++)
{
heavy>>v[i].x>>v[i].y;
v[i].heavymetal=v[i].y-v[i].x;
w[2*i-1]=v[i].x;
w[2*i]=v[i].y;
}
sort(w+1,w+2*n+1);
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++)
{
v[i].x=SLIPKNOT(v[i].x);
v[i].y=SLIPKNOT(v[i].y);
}
for(i=1;i<=n;i++)
{
while(k<=v[i].y)
slipknot[k]=max(slipknot[k],slipknot[k-1]),k++;
slipknot[v[i].y]=max(slipknot[v[i].y],slipknot[v[i].x]+v[i].heavymetal);
}
metal<<slipknot[v[n].y];
return 0;
}