Pagini recente » Cod sursa (job #662038) | Cod sursa (job #3285228) | Cod sursa (job #2184072) | Cod sursa (job #2881495) | Cod sursa (job #2585229)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
long long n,i,dp[100005],mx,j,l,pmax;
struct cv {
long long in,sf;
} v[100005];
bool comp(cv a,cv b) {
if(a.sf>b.sf) return false;
if(a.sf==b.sf and a.in>b.in) return false;
return true;
}
long long binar(long long caut) {
long long p=0;
for(long long k=pmax; k>=0; k--)
if(p+(1<<k)<=n and v[p+(1<<k)].sf<=caut) p=p+(1<<k);
return p;
}
int main() {
f >> n;
while( (1<<(pmax+1)) <=n ) pmax++;
for(i=1; i<=n; i++)
f >> v[i].in >> v[i].sf;
sort(v+1,v+n+1,comp);
dp[1]=v[1].sf-v[1].in;
for(i=2; i<=n; i++)
dp[i]=max(dp[i-1],dp[binar(v[i].in)]+v[i].sf-v[i].in) ;
g << dp[n];
return 0;
}