Pagini recente » Autentificare | Cod sursa (job #1129969) | Istoria paginii runda/ion | Profil Churchil | Cod sursa (job #2521331)
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
#define N 100100
pair <long long, long long> v[N];
long long d[N], maxim[N];
int i, n, poz;
int bs (long long x){
if (x < v[0].first)
return -1;
int ans = 0;
for (int it = n; it > 0; it >>= 1)
while (it + ans < n && x >= v[it + ans].first)
ans += it;
return ans;
}
int main()
{
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
fin >> n;
for (i = 0; i < n; ++i)
fin >> v[i].second >> v[i].first;
sort (v, v + n);
d[0] = v[0].first - v[0].second;
maxim[0] = d[0];
for (i = 1; i < n; ++i){
poz = bs (v[i].second);
d[i] = v[i].first - v[i].second;
if (poz > -1)
d[i] += maxim[poz];
maxim[i] = max (d[i], maxim[i - 1]);
}
fout << maxim[n - 1];
return 0;
}