Pagini recente » Cod sursa (job #1523742) | Cod sursa (job #996932) | Diferente pentru home intre reviziile 196 si 197 | Istoria paginii utilizator/ilinca_andrei | Cod sursa (job #2021579)
#include <cstdio>
#include <algorithm>
const int INF = 2e9;
const int MAXN = 1e5;
struct Form {
int x, y;
} v[MAXN + 1];
int d[MAXN + 1];
inline int cmp(Form a, Form b) {
return a.y < b.y;
}
inline int max(int a, int b) {
return a > b ? a : b;
}
inline int bins(int st, int dr, int val) {
int m, l = INF;
while (st <= dr) {
m = (st + dr) >> 1;
if (v[m].y <= val) {
st = m + 1;
l = m;
} else {
dr = m - 1;
}
}
return l;
}
int main() {
int n, poz, ans;
FILE *f = fopen("heavymetal.in", "r");
fscanf(f, "%d", &n);
for (int i = 1; i <= n; ++i) {
fscanf(f, "%d%d", &v[i].x, &v[i].y);
}
fclose(f);
std::sort(v + 1, v + n + 1, cmp);
ans = 0;
for (int i = 1; i <= n; ++i) {
poz = bins(1, i - 1, v[i].x);
if (poz == INF) {
d[i] = max(d[i - 1], v[i].y - v[i].x);
} else {
d[i] = max(d[i - 1], v[i].y - v[i].x + d[poz]);
}
if (ans < d[i]) {
ans = d[i];
}
}
f = fopen("heavymetal.out", "w");
fprintf(f, "%d\n", ans);
fclose(f);
return 0;
}