// Minimizar el retraso máximo en una sola máquina, sin tiempo muerto.
#pragma once

#include <algorithm>
#include <cstddef>
#include <limits>
#include <numeric>
#include <vector>

struct Job {
    long long duration;
    long long deadline;
};

// Un horario es un orden de las tareas: la primera empieza en 0 y cada una empieza
// cuando termina la anterior. retraso = fin - plazo, negativo si terminó con holgura.
inline std::vector<long long> latenesses(const std::vector<Job>& jobs, const std::vector<int>& order) {
    std::vector<long long> result;
    long long now = 0;
    for (int id : order) {
        const Job& job = jobs[static_cast<std::size_t>(id)];
        now += job.duration;
        result.push_back(now - job.deadline);
    }
    return result;
}

inline long long max_lateness(const std::vector<Job>& jobs, const std::vector<int>& order) {
    std::vector<long long> values = latenesses(jobs, order);
    return *std::max_element(values.begin(), values.end());
}

// Una inversión es un par con la tarea de plazo mayor antes, estrictamente:
// dos tareas con el mismo plazo no forman una inversión.
inline bool inverted(const std::vector<Job>& jobs, int first, int second) {
    return jobs[static_cast<std::size_t>(first)].deadline > jobs[static_cast<std::size_t>(second)].deadline;
}

inline int count_inversions(const std::vector<Job>& jobs, const std::vector<int>& order) {
    int count = 0;
    for (std::size_t i = 0; i < order.size(); i++) {
        for (std::size_t j = i + 1; j < order.size(); j++) {
            if (inverted(jobs, order[i], order[j])) count++;
        }
    }
    return count;
}

// Posición de la primera inversión adyacente, o order.size() si no hay.
inline std::size_t first_adjacent_inversion(const std::vector<Job>& jobs, const std::vector<int>& order) {
    for (std::size_t i = 0; i + 1 < order.size(); i++) {
        if (inverted(jobs, order[i], order[i + 1])) return i;
    }
    return order.size();
}

// Ordena las tareas según una clave; a igual clave, se conserva el orden de la lista.
template <typename Key>
std::vector<int> order_by(const std::vector<Job>& jobs, Key key) {
    std::vector<int> order(jobs.size());
    std::iota(order.begin(), order.end(), 0);
    std::stable_sort(order.begin(), order.end(), [&](int a, int b) {
        return key(jobs[static_cast<std::size_t>(a)]) < key(jobs[static_cast<std::size_t>(b)]);
    });
    return order;
}

inline std::vector<int> order_by_deadline(const std::vector<Job>& jobs) {
    return order_by(jobs, [](const Job& job) { return job.deadline; });
}

inline std::vector<int> order_by_duration(const std::vector<Job>& jobs) {
    return order_by(jobs, [](const Job& job) { return job.duration; });
}

inline std::vector<int> order_by_slack(const std::vector<Job>& jobs) {
    return order_by(jobs, [](const Job& job) { return job.deadline - job.duration; });
}

// El árbitro: prueba todas las permutaciones. Solo sirve con n pequeño.
inline long long brute_min_max_lateness(const std::vector<Job>& jobs) {
    std::vector<int> order(jobs.size());
    std::iota(order.begin(), order.end(), 0);
    long long best = std::numeric_limits<long long>::max();
    do {
        best = std::min(best, max_lateness(jobs, order));
    } while (std::next_permutation(order.begin(), order.end()));
    return best;
}