Pagini recente » Cod sursa (job #1687022) | Cod sursa (job #2722624) | Cod sursa (job #2385586) | Cod sursa (job #3121741) | Cod sursa (job #2930073)
#include<bits/stdc++.h>
#define int long long
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n,v[200005],k,con,nou[200005],dp[200005];///dp[i]=timpul maxim pana la momentul i
struct elem
{
int x,y,t;
}w[100005];
int cmp(elem a, elem b)
{
return a.y<b.y;
}
int caut_bin(int x)
{
int st=1,dr=con,retin;
while(st<=dr)
{
int mij=(st+dr)/2;
if(x==nou[mij])
{
retin=mij;
break;
}
if(x<nou[mij])
dr=mij-1;
else
st=mij+1;
}
return retin;
}
signed main()
{
int i,x,y;
f>>n;
for(i=1;i<=n;i++)
{
f>>x>>y;
k++;
v[k]=x;
k++;
v[k]=y;
w[i].x=x;
w[i].y=y;
w[i].t=w[i].y-w[i].x;
}
sort(w+1,w+n+1,cmp);
sort(v+1,v+k+1);
for(i=1;i<=k;i++)
{
con++;
nou[con]=v[i];
while(i+1<=k && v[i+1]==v[i])
i++;
}
for(i=1;i<=n;i++)
w[i].x=caut_bin(w[i].x),w[i].y=caut_bin(w[i].y);
dp[0]=0;
k=1;
for(i=1;i<=n;i++)
{
while(k<w[i].y)
{
dp[k]=max(dp[k],dp[k-1]);
k++;
}
dp[k]=max(dp[k],dp[k-1]);
if(k==w[i].y)
dp[k]=max(dp[k],dp[w[i].x]+w[i].t);
k++;
}
g<<dp[k-1];
return 0;
}