Pagini recente » Cod sursa (job #367748) | Cod sursa (job #2389412) | Cod sursa (job #1745640) | Cod sursa (job #493009) | Cod sursa (job #614531)
Cod sursa(job #614531)
#include<fstream>
#include<algorithm>
using namespace std;
const int maxn = 100005;
pair <int,int> segm[maxn];
long long maxim[maxn], c[maxn];
int cmp(pair <int,int> a, pair <int,int> b) {
return (a.second == b.second && a.first < b.first) ||
(a.second < b.second);
}
int bsearch(int left, int right, int x) {
int m, pos = 0;
while (left <= right) {
m = (left+right)/2;
if (segm[m].second <= x) {
pos = m;
left = m+1;
} else {
right = m-1;
}
}
return pos;
}
int main() {
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n, x, y;
f >> n;
for (int i = 1; i <= n; i++) {
f >> x >> y;
segm[i] = make_pair(x, y);
}
sort(segm+1, segm+n+1, cmp);
c[1] = segm[1].second-segm[1].first;
maxim[1] = c[1];
for (int i = 2; i <= n; i++) {
int pos = bsearch(1, i-1, segm[i].first);
c[i] = maxim[pos] + segm[i].second - segm[i].first;
maxim[i] = maxim[i-1];
if (c[i] > maxim[i-1]) {
maxim[i] = c[i];
}
}
g << maxim[n] << '\n';
return 0;
}