Pagini recente » Cod sursa (job #2080113) | Cod sursa (job #1261259) | Cod sursa (job #1734201) | Cod sursa (job #93416) | Cod sursa (job #1851920)
#include <cstdio>
#include <algorithm>
const int MAX_N = 100000;
struct Interval {
int a, b;
} v[MAX_N];
int d[1+MAX_N];
bool cmp(Interval a, Interval b) {
return a.b < b.b;
}
int bins(int st, int dr, int x) {
int mid;
while(dr - st > 1) {
mid = (st + dr) / 2;
if(v[mid].b <= x)
st = mid;
else
dr = mid;
}
return st;
}
int main() {
int n, poz, lft;
FILE *fin = fopen("heavymetal.in", "r");
fscanf(fin, "%d", &n);
for(int i = 1; i <= n; ++i)
fscanf(fin, "%d%d", &v[i].a, &v[i].b);
fclose(fin);
std::sort(v + 1, v + 1 + n, cmp);
for(int i = 1; i <= n; ++i) {
d[i] = d[i - 1];
lft = bins(0, i, v[i].a);
if(d[lft] + v[i].b - v[i].a > d[i])
d[i] = d[lft] + v[i].b - v[i].a;
}
FILE *fout = fopen("heavymetal.out", "w");
fprintf(fout, "%d", d[n]);
fclose(fout);
return 0;
}