Pagini recente » Cod sursa (job #2719592) | Cod sursa (job #442533) | Cod sursa (job #1028756) | Cod sursa (job #2589275) | Cod sursa (job #2515971)
#include <fstream>
#include <algorithm>
#include <cmath>
#define ll long long
#define N 100005
using namespace std;
ll a, b, mij, n, dp[N];
pair<int, int> v[N];
ll max ( ll a, ll b){
if ( a > b )
return a;
else return b;
}
int main(){
ifstream in ("heavymetal.in");
in >> n;
for (int i = 1; i <= n; i++)
in >> v[i].second >> v[i].first;
sort (v + 1, v + n + 1);
for (int i = 1; i <= n; i++ )
swap (v[i].first, v[i].second);
in.close();
ofstream out ("heavymetal.out");
dp[1] = v[1].second - v[1].first;
for (int i = 2; i <= n; i++ ){
dp[i] = dp[i - 1];
dp[i] = max (dp[i], v[i].second - v[i].first);
a = 1;
b = i - 1;
while ( a <= b ){
mij = ( a + b ) / 2;
if ( v[mij].second <= v[mij].first )
a = mij + 1;
else
b = mij - 1;
}
dp[i] = max( dp[i], dp[b] + v[i].second - v[i].first);
}
out << dp[n];
out.close();
return 0;
}