// Intervalos con pesos: clases [start, finish) con un valor. Se busca el máximo valor total sin
// que dos se crucen. Igual que en la semana 4, los intervalos son semiabiertos.
#pragma once

#include <algorithm>
#include <cstddef>
#include <vector>

struct WeightedInterval {
    int start;
    int finish;
    long long value;
};

inline bool compatible(const WeightedInterval& a, const WeightedInterval& b) {
    return a.finish <= b.start || b.finish <= a.start;
}

inline void sort_by_finish(std::vector<WeightedInterval>& classes) {
    std::stable_sort(classes.begin(), classes.end(), [](const WeightedInterval& a, const WeightedInterval& b) {
        return a.finish < b.finish;
    });
}

// p[j]: cuántas clases, en el orden por fin, terminan a más tardar cuando empieza la clase j.
// Son las primeras p[j] del orden. Se halla con búsqueda binaria sobre los fines.
inline std::vector<std::size_t> compatible_prefix(const std::vector<WeightedInterval>& sorted) {
    std::vector<int> finishes;
    for (const WeightedInterval& c : sorted) finishes.push_back(c.finish);
    std::vector<std::size_t> p;
    for (const WeightedInterval& c : sorted) {
        // upper_bound: el primer fin mayor que start. Un fin igual a start sí es compatible.
        const auto it = std::upper_bound(finishes.begin(), finishes.end(), c.start);
        p.push_back(static_cast<std::size_t>(it - finishes.begin()));
    }
    return p;
}

// El mismo cálculo con lower_bound, un error frecuente: trata los bordes como si se cruzaran.
inline std::vector<std::size_t> compatible_prefix_closed(const std::vector<WeightedInterval>& sorted) {
    std::vector<int> finishes;
    for (const WeightedInterval& c : sorted) finishes.push_back(c.finish);
    std::vector<std::size_t> p;
    for (const WeightedInterval& c : sorted) {
        const auto it = std::lower_bound(finishes.begin(), finishes.end(), c.start);
        p.push_back(static_cast<std::size_t>(it - finishes.begin()));
    }
    return p;
}

// La definición, sin búsqueda binaria, para comparar en las pruebas.
inline std::vector<std::size_t> compatible_prefix_linear(const std::vector<WeightedInterval>& sorted) {
    std::vector<std::size_t> p;
    for (const WeightedInterval& c : sorted) {
        std::size_t count = 0;
        for (const WeightedInterval& other : sorted) {
            if (other.finish <= c.start) count++;
        }
        p.push_back(count);
    }
    return p;
}

// best[j]: el máximo valor usando solo las primeras j clases del orden por fin.
inline std::vector<long long> weighted_table(const std::vector<WeightedInterval>& sorted,
                                             const std::vector<std::size_t>& p) {
    std::vector<long long> best(sorted.size() + 1, 0);
    for (std::size_t j = 1; j <= sorted.size(); j++) {
        best[j] = std::max(best[j - 1], sorted[j - 1].value + best[p[j - 1]]);
    }
    return best;
}

// Camina la tabla hacia atrás. Devuelve las posiciones elegidas, en orden creciente.
inline std::vector<std::size_t> weighted_choose(const std::vector<WeightedInterval>& sorted,
                                                const std::vector<std::size_t>& p,
                                                const std::vector<long long>& best) {
    std::vector<std::size_t> chosen;
    std::size_t j = sorted.size();
    while (j > 0) {
        if (best[j] == best[j - 1]) {
            j--;
        } else {
            chosen.push_back(j - 1);
            j = p[j - 1];
        }
    }
    std::reverse(chosen.begin(), chosen.end());
    return chosen;
}

inline long long weighted_best(std::vector<WeightedInterval> classes) {
    sort_by_finish(classes);
    return weighted_table(classes, compatible_prefix(classes)).back();
}

// El greedy de la semana 4: la que termina antes, sin mirar el valor.
inline long long greedy_earliest_finish(std::vector<WeightedInterval> classes) {
    sort_by_finish(classes);
    long long total = 0;
    bool any = false;
    int free_from = 0;
    for (const WeightedInterval& c : classes) {
        if (!any || free_from <= c.start) {
            total += c.value;
            free_from = c.finish;
            any = true;
        }
    }
    return total;
}

// Otra idea razonable: la de mayor valor primero, saltando lo que se cruce.
inline long long greedy_highest_value(std::vector<WeightedInterval> classes) {
    std::stable_sort(classes.begin(), classes.end(), [](const WeightedInterval& a, const WeightedInterval& b) {
        return a.value > b.value;
    });
    std::vector<WeightedInterval> chosen;
    long long total = 0;
    for (const WeightedInterval& c : classes) {
        bool fits = true;
        for (const WeightedInterval& other : chosen) {
            if (!compatible(c, other)) fits = false;
        }
        if (fits) {
            chosen.push_back(c);
            total += c.value;
        }
    }
    return total;
}

// Prueba los 2^n subconjuntos. Solo sirve de árbitro con n pequeño.
inline long long weighted_brute(const std::vector<WeightedInterval>& classes) {
    const std::size_t n = classes.size();
    long long best = 0;
    for (unsigned mask = 0; mask < (1U << n); mask++) {
        long long total = 0;
        bool valid = true;
        for (std::size_t i = 0; i < n && valid; i++) {
            if (!((mask >> i) & 1U)) continue;
            total += classes[i].value;
            for (std::size_t j = i + 1; j < n; j++) {
                if (((mask >> j) & 1U) && !compatible(classes[i], classes[j])) valid = false;
            }
        }
        if (valid) best = std::max(best, total);
    }
    return best;
}