Pagini recente » Cod sursa (job #607330) | Cod sursa (job #2513543) | Cod sursa (job #2273137) | Cod sursa (job #1996545) | Cod sursa (job #2145250)
/// d[i]= perioada maxima de concertare de la 1 la i.
#include <cstdio>
#include <algorithm>
#define NMAX 100002
using namespace std;
int dp[NMAX];
pair<int,int> v[NMAX];
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,cc,st,dr,mid;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d %d",&v[i].second,&v[i].first);
sort(v+1,v+n+1);
dp[1]=v[1].first-v[1].second;
for(int i=2;i<=n;i++)
{
cc=v[i].second;
st=1;dr=i-1;
while(st<=dr)
{
mid=(st+dr)/2;
if(v[mid].first<=cc)
st=mid+1;
else
dr=mid-1;
}
dp[i]=max(v[i].first-v[i].second+dp[dr],dp[i-1]);
}
printf("%d",dp[n]);
return 0;
}