Pagini recente » Cod sursa (job #784035) | Cod sursa (job #1678122) | Cod sursa (job #2411117) | Cod sursa (job #3185578) | Cod sursa (job #1860962)
#include <stdio.h>
#include <ctype.h>
#define MAX_N 100000
#define MAX_BUFF 65536
struct cell {
int x, y;
cell() {
}
bool operator < (const cell &other) {
return this -> y < other.y;
}
};
int N, ptr;
char buff[MAX_BUFF];
int max[MAX_N + 1], cost[MAX_N + 1];
cell sorted[MAX_N + 1];
char getChar(FILE *f) {
if (ptr == MAX_BUFF) {
fread(buff, 1, MAX_BUFF, f);
ptr = 0;
}
return buff[ptr++];
}
int freef(FILE *f) {
int result = 0;
char c;
do {
c = getChar(f);
} while (!isdigit(c));
do {
result = (result << 3) + (result << 1) + c - '0';
c = getChar(f);
} while (isdigit(c));
return result;
}
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");
N = freef(f);
for (i = 1; i <= N; i++) {
sorted[i].x = freef(f);
sorted[i].y = freef(f);
}
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", max[N]);
fclose(stdout);
return 0;
}