Pagini recente » Cod sursa (job #1595837) | Cod sursa (job #2282072) | Cod sursa (job #3158737) | Cod sursa (job #2468280) | Cod sursa (job #1898324)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMax = 1e5 + 5;
int Best[NMax];
pair < int, int > v[NMax];
int Binary(int hi, const int &value) {
int lo = 1;
int best = 0;
while(lo <= hi) {
int mid = (lo + hi) >> 1;
if(v[mid].first > value) {
hi = mid - 1;
} else {
best = mid;
lo = mid + 1;
}
}
return best;
}
int main() {
int n;
fin >> n;
v[0] = {-1, -1};
for(int i = 1; i <= n; i++) fin >> v[i].second >> v[i].first;
sort(v + 1, v + n + 1);
for(int i = 1; i <= n; i++) {
Best[i] = v[i].first - v[i].second + Best[Binary(i - 1, v[i].second)];
Best[i] = max(Best[i], Best[i - 1]);
}
fout << Best[n];
return 0;
}