Pagini recente » Cod sursa (job #914377) | Cod sursa (job #2388798) | Cod sursa (job #2448574) | Cod sursa (job #1213602) | Cod sursa (job #2511572)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n;
vector < pair <int,int> > v;
long long dp[NMAX],maxim;
int main()
{
f>>n;
v.push_back({0,0});
for(int i=1;i<=n;i++)
{
int x,y;
f>>x>>y;
v.push_back({y,x});
}
sort(v.begin(),v.end());
for(int i=1;i<=n;i++)
{
int st=0;
int dr=i-1;
int sol=0;
while(st<=dr)
{
int mid=(st+dr)/2;
if(v[mid].first<=v[i].second)
{
sol=mid;
st=mid+1;
}
else
dr=mid-1;
}
dp[i]=max(dp[i-1],v[i].first-v[i].second+dp[sol]);
maxim=max(dp[i],maxim);
}
g<<maxim;
return 0;
}