Pagini recente » Cod sursa (job #1689634) | Cod sursa (job #2882661) | Cod sursa (job #375983) | Cod sursa (job #3174370) | Cod sursa (job #2585226)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
int n,i,dp[100005],mx,j,l,pmax;
struct cv {
int 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;
}
int binar(int caut) {
int p=0;
for(int k=pmax; k>=0; k--)
if(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;
}