Pagini recente » Cod sursa (job #2466569) | Profil sandupetrasco | Cod sursa (job #1815552) | Cod sursa (job #1290412) | Cod sursa (job #2552382)
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct concert {int st, dr;};
const int NMAX = 100005;
concert v[NMAX];
int vmax[NMAX];
bool cmp(concert a, concert b) {
return a.dr < b.dr;
}
int main() {
freopen ("heavymetal.in", "r", stdin);
freopen ("heavymetal.out", "w", stdout);
int n, i, left, right, mid, r;
scanf ("%d", &n);
for (i = 1; i <= n; i++)
scanf ("%d%d", &v[i].st, &v[i].dr);
sort (v + 1, v + n + 1, cmp);
for (i = 1; i <= n; i++) {
left = 0;
right = i - 1;
while (left <= right) {
mid = (left + right) / 2;
if (v[mid].dr <= v[i].st) {
r = mid;
left = mid + 1;
}
else
right = mid - 1;
}
vmax[i] = max(vmax[r] + v[i].dr - v[i].st, vmax[i - 1]);
}
printf ("%d", vmax[n]);
return 0;
}