Pagini recente » Cod sursa (job #390) | Cod sursa (job #1941280) | Cod sursa (job #1116567) | Cod sursa (job #797178) | Cod sursa (job #1860948)
#include <stdio.h>
#define MAX_N 100000
struct cell {
int x, y;
cell() {
}
bool operator < (const cell &other) {
return this -> y < other.y;
}
};
int N;
int max[MAX_N + 1], cost[MAX_N + 1];
cell sorted[MAX_N + 1];
int MAX(int X, int Y) {
return X > Y ? X : Y;
}
void sort(int begin, int end) {
int b = begin, e = end;
cell tmp, pivot = sorted[(b + e) >> 1];
while (b <= e) {
while (sorted[b] < pivot) {
b++;
}
while (pivot < sorted[e]) {
e--;
}
if (b <= e) {
tmp = sorted[b];
sorted[b++] = sorted[e];
sorted[e--] = tmp;
}
}
if (begin < e) {
sort(begin, e);
}
if (b < end) {
sort(b, end);
}
}
int binSearch(int lim, int v) {
int x = 0, pas = 65536;
while (pas) {
if (x + pas <= lim && sorted[x + pas].y <= v) {
x += pas;
}
pas >>= 1;
}
return x;
}
int main(void) {
int i;
FILE *f = fopen("heavymetal.in", "r");
fscanf(f, "%d", &N);
for (i = 1; i <= N; i++) {
fscanf(f, "%d %d", &sorted[i].x, &sorted[i].y);
}
fclose(f);
sort(1, N);
cost[1] = sorted[1].y - sorted[1].x;
max[1] = cost[1];
for (i = 2; i <= N; i++) {
int pos = binSearch(i - 1, sorted[i].x);
cost[i] = sorted[i].y - sorted[i].x + max[pos];
max[i] = MAX(max[i - 1], cost[i]);
}
freopen("heavymetal.out", "w", stdout);
fprintf(stdout, "%d\n", cost[N]);
fclose(stdout);
return 0;
}