Pagini recente » Borderou de evaluare (job #118934) | Borderou de evaluare (job #2258596) | Borderou de evaluare (job #854785) | Borderou de evaluare (job #2039646) | Cod sursa (job #2518369)
#include<bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct in{
int x,y;
} v[100005];
bool cmp(in a,in b){
return a.y < b.y;
}
int n,dp[100005];
int main()
{
f>>n;
for(int i=1;i<=n;i++) f>>v[i].x>>v[i].y;
sort(v+1,v+1+n,cmp);
dp[1]=v[1].y-v[1].x;
for(int i=2;i<=n;i++)
{
dp[i]=dp[i-1];
int d=v[i].y-v[i].x;
int st=1,dr=i,M=0;
while(st<=dr)
{
int m=(st+dr)/2;
if(v[m].y<=v[i].x)
{
st=m+1;
M=max(M,m);
}
else dr=m-1;
}
dp[i]=max(dp[i],dp[M]+d);
}
g<<dp[n];
}