Pagini recente » Cod sursa (job #1119007) | Cod sursa (job #2620063) | Cod sursa (job #1022428) | Cod sursa (job #1506933) | Cod sursa (job #1876863)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#define N 100000
#define INF 0x3f3f3f3f
#define iter vector<pair<int, int> >::iterator
using namespace std;
int A[N], B[N], I[N], H[N];
bool comp(int a, int b) {
return B[a] < B[b];
}
int main() {
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n;
fin >> n;
for (int i = 1; i <= n; ++i) {
int a, b;
fin >> a >> b;
A[i] = a;
B[i] = b;
I[i] = i;
}
sort(I + 1, I + n + 1, comp);
H[I[1]] = B[I[1]] - A[I[1]];
for (int i = 2; i <= n; ++i) {
// Binary-search for the event ending with A[i]
int step, val;
for (step = 1; step < i; step <<= 1);
for (val = 0; step; step >>= 1) {
int v = val + step;
if (v < i && B[I[v]] <= A[I[i]])
val = v;
}
H[I[i]] = max(H[I[i - 1]], H[I[val]] + B[I[i]] - A[I[i]]);
}
fout << H[I[n]] << "\n";
return 0;
}