Cod sursa(job #1891223)

Utilizator savigunFeleaga Dragos-George savigun Data 23 februarie 2017 20:26:28
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

struct concert{
    int start, end;
} c[100001];

int n;
long long best[100001];
const int L = 1 << 17;

bool compare(concert a, concert b) {
    return a.end < b.end;
}

int binary_search(int val) {
    int step = L;
    int pos = 0;
    while (step != 0) {
        if (pos + step <= n && c[pos + step].end <= val) {
            pos += step;
        }
        step /= 2;
    }

    return pos;
}

int main()
{
    in >> n;

    for (int i = 1; i <= n; ++i) {
        in >> c[i].start >> c[i].end;
    }

    sort(c + 1, c + n + 1, compare);

    best[1] = c[1].end - c[1].start;
    for (int i = 2; i <= n; ++i) {
        int before = binary_search(c[i].start);

        best[i] = max(
            (c[i].end - c[i].start) + best[before],
            best[i - 1]
        );
    }

    out << best[n];

    return 0;
}