Cod sursa(job #1223736)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 28 august 2014 18:16:38
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int NMAX = 100003;

struct band {

    int left, right;

};

bool operator < (const band &a, const band &b) {

    if (a.right < b.right)
        return 1;
    if (a.right == b.right)
        return a.left < b.left;
    return 0;

}

band V[NMAX];
int sel[NMAX], D[NMAX];

int binarySearch (int right, const int &val) {

    int left = 1, middle;
    while (left <= right) {
        middle = left + right >> 1;
        if (val < V[middle].right)
            right = middle - 1;
        else
            left = middle + 1;
    }
    return right;

}

int main () {

    freopen ("heavymetal.in", "r", stdin);
    freopen ("heavymetal.out", "w", stdout);
    int N, i, j, k;
    scanf ("%d", &N);
    for (i = 1; i <= N; ++i)
        scanf ("%d%d", &V[i].left, &V[i].right);
    sort (V + 1, V + N + 1);
    for (i = 1; i <= N; ++i)
        D[i] = max (D[i - 1], D[binarySearch (i - 1, V[i].left)] + V[i].right - V[i].left);
    printf ("%d", D[N]);

}