Pagini recente » Cod sursa (job #2087695) | Cod sursa (job #145481) | Cod sursa (job #756901) | Cod sursa (job #1786682) | Cod sursa (job #2515972)
#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[i].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;
}