Cod sursa(job #2351205)

Utilizator LittleWhoFeraru Mihail LittleWho Data 22 februarie 2019 08:38:21
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef signed long long ll;
typedef unsigned int uint;
const int nmax = 100005;
struct interval {
    uint start;
    uint finish;
};
struct comp {
    bool operator()(const interval &left, const interval &right) {
        if (left.finish == right.finish)
            return left.start < right.start;
        return left.finish < right.finish;
    }
};

interval v[nmax];
uint dp[nmax];
uint n;

uint find_best(uint value, uint right) {
    uint left = 1;
    uint mid;

    while (left + 1 < right) {
        mid = (left + right) / 2;

        if (v[mid].finish > value) {
            right = mid - 1;
        } else {
            right = mid + 1;
        }
    }

    return right;
}

int main() {
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);

    scanf("%u", &n);
    for (uint i = 1; i <= n; i++) {
        scanf("%u %u", &v[i].start, &v[i].finish);
    }

    sort(v, v + n, comp());
    dp[1] = v[1].finish - v[1].start;
    for (uint i = 2; i <= n; i++) {
        uint j = find_best(v[i].start, i - 1); // find best j such that v[j].finish <= v[i].start
        dp[i] = max(dp[i - 1], dp[j] + v[i].finish - v[i].start);
    }
    printf("%u\n", dp[n]);

    /*for (uint i = 0;i<n;i++){
    cout<<v[i].start <<" "<<v[i].finish<<endl;
    }*/

    return 0;
}