Pagini recente » Cod sursa (job #891395) | Cod sursa (job #2553096) | Cod sursa (job #2317535) | Cod sursa (job #2523983) | Cod sursa (job #1876867)
/*
* Dynamic programming paired with binary search. The problems I had were with
* the definition of the DP table. First I defined it such that the last
*/
#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 = 0; i < n; ++i) {
int a, b;
fin >> a >> b;
A[i] = a;
B[i] = b;
I[i] = i;
}
sort(I, I + n, comp);
H[I[0]] = B[I[0]] - A[I[0]];
for (int i = 1; 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;
}
if (B[I[val]] <= A[I[i]])
H[I[i]] = max(H[I[i - 1]], H[I[val]] + B[I[i]] - A[I[i]]);
else
H[I[i]] = max(H[I[i - 1]], B[I[i]] - A[I[i]]);
}
fout << H[I[n - 1]] << "\n";
return 0;
}