// Programación dinámica sobre intervalos: cadena de matrices y árbol binario de búsqueda óptimo.
#pragma once

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

using CostTable = std::vector<std::vector<long long>>;
using SplitTable = std::vector<std::vector<int>>;

constexpr long long NO_COST = std::numeric_limits<long long>::max();

// ---------- Cadena de matrices. La matriz i mide d[i] x d[i + 1]. ----------

struct ChainTables {
    CostTable cost;    // cost[i][j]: el mínimo para multiplicar las matrices i..j, ambas incluidas
    SplitTable split;  // split[i][j]: la k de la última multiplicación
};

inline long long merge_cost(const std::vector<long long>& d, int i, int k, int j) {
    return d[i] * d[k + 1] * d[j + 1];
}

// Por largo creciente: todo lo que se lee es más corto que lo que se escribe.
inline ChainTables matrix_chain(const std::vector<long long>& d, long long* combinations = nullptr) {
    const int n = static_cast<int>(d.size()) - 1;
    ChainTables t{CostTable(n, std::vector<long long>(n, 0)), SplitTable(n, std::vector<int>(n, -1))};
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i + length - 1 < n; i++) {
            const int j = i + length - 1;
            t.cost[i][j] = NO_COST;
            for (int k = i; k < j; k++) {
                if (combinations) (*combinations)++;
                const long long c = t.cost[i][k] + t.cost[k + 1][j] + merge_cost(d, i, k, j);
                if (c < t.cost[i][j]) {
                    t.cost[i][j] = c;
                    t.split[i][j] = k;
                }
            }
        }
    }
    return t;
}

// También sirve: i de mayor a menor y j de menor a mayor. Lo leído tiene i mayor, o j menor.
inline long long matrix_chain_i_descending(const std::vector<long long>& d) {
    const int n = static_cast<int>(d.size()) - 1;
    CostTable cost(n, std::vector<long long>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            cost[i][j] = NO_COST;
            for (int k = i; k < j; k++) {
                cost[i][j] = std::min(cost[i][j], cost[i][k] + cost[k + 1][j] + merge_cost(d, i, k, j));
            }
        }
    }
    return n == 0 ? 0 : cost[0][n - 1];
}

// Error: i de menor a mayor y j de menor a mayor. Las casillas sin llenar valen 0 y se leen igual.
struct NaiveOrderRun {
    long long answer;
    long long empty_reads;
    std::vector<std::string> first_reads;
};

inline NaiveOrderRun matrix_chain_naive_order(const std::vector<long long>& d) {
    const int n = static_cast<int>(d.size()) - 1;
    CostTable cost(n, std::vector<long long>(n, 0));
    std::vector<std::vector<char>> filled(n, std::vector<char>(n, 0));
    for (int i = 0; i < n; i++) filled[i][i] = 1;
    NaiveOrderRun run{0, 0, {}};
    const auto read = [&](int writing_i, int writing_j, int i, int j) {
        if (!filled[i][j]) {
            run.empty_reads++;
            run.first_reads.push_back("M[" + std::to_string(writing_i) + "][" + std::to_string(writing_j) +
                                      "] lee M[" + std::to_string(i) + "][" + std::to_string(j) + "], vacía");
        }
        return cost[i][j];
    };
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long long best = NO_COST;
            for (int k = i; k < j; k++) {
                best = std::min(best, read(i, j, i, k) + read(i, j, k + 1, j) + merge_cost(d, i, k, j));
            }
            cost[i][j] = best;
            filled[i][j] = 1;
        }
    }
    run.answer = n == 0 ? 0 : cost[0][n - 1];
    return run;
}

inline std::string parenthesize(const SplitTable& split, int i, int j) {
    if (i == j) return "A" + std::to_string(i);
    const int k = split[i][j];
    return "(" + parenthesize(split, i, k) + " " + parenthesize(split, k + 1, j) + ")";
}

// Árbitro: arma cada parentización y calcula su costo multiplicando de verdad las dimensiones.
struct ChainPlan {
    long long rows;
    long long columns;
    long long cost;
};

inline std::vector<ChainPlan> all_chain_plans(const std::vector<long long>& d, int i, int j) {
    if (i == j) return {{d[i], d[i + 1], 0}};
    std::vector<ChainPlan> plans;
    for (int k = i; k < j; k++) {
        for (const ChainPlan& left : all_chain_plans(d, i, k)) {
            for (const ChainPlan& right : all_chain_plans(d, k + 1, j)) {
                plans.push_back({left.rows, right.columns,
                                 left.cost + right.cost + left.rows * left.columns * right.columns});
            }
        }
    }
    return plans;
}

inline long long chain_brute(const std::vector<long long>& d) {
    long long best = NO_COST;
    for (const ChainPlan& plan : all_chain_plans(d, 0, static_cast<int>(d.size()) - 2)) {
        best = std::min(best, plan.cost);
    }
    return best;
}

// Greedy que falla: hacer siempre primero la multiplicación vecina más barata.
inline long long chain_cheapest_first(std::vector<long long> d) {
    long long total = 0;
    while (d.size() > 2) {
        std::size_t best = 1;
        for (std::size_t m = 1; m + 1 < d.size(); m++) {
            if (d[m - 1] * d[m] * d[m + 1] < d[best - 1] * d[best] * d[best + 1]) best = m;
        }
        total += d[best - 1] * d[best] * d[best + 1];
        d.erase(d.begin() + static_cast<std::ptrdiff_t>(best));
    }
    return total;
}

// ---------- Árbol binario de búsqueda óptimo. Rangos semiabiertos [i, j). ----------

struct BstTables {
    CostTable cost;  // cost[i][j]: el mínimo de la suma de frecuencia por profundidad, claves i..j-1
    SplitTable root; // root[i][j]: la clave que va en la raíz de ese rango
};

inline std::vector<long long> prefix_sums(const std::vector<long long>& f) {
    std::vector<long long> sum(f.size() + 1, 0);
    for (std::size_t i = 0; i < f.size(); i++) sum[i + 1] = sum[i] + f[i];
    return sum;
}

inline BstTables optimal_bst(const std::vector<long long>& f) {
    const int n = static_cast<int>(f.size());
    const std::vector<long long> sum = prefix_sums(f);
    BstTables t{CostTable(n + 1, std::vector<long long>(n + 1, 0)), SplitTable(n + 1, std::vector<int>(n + 1, -1))};
    for (int length = 1; length <= n; length++) {
        for (int i = 0; i + length <= n; i++) {
            const int j = i + length;
            long long best = NO_COST;
            for (int r = i; r < j; r++) {
                const long long c = t.cost[i][r] + t.cost[r + 1][j];
                if (c < best) {
                    best = c;
                    t.root[i][j] = r;
                }
            }
            t.cost[i][j] = best + sum[j] - sum[i];
        }
    }
    return t;
}

// Las profundidades de cada clave en el árbol que dice la tabla. La raíz tiene profundidad 1.
inline void bst_depths(const SplitTable& root, int i, int j, int depth, std::vector<int>& out) {
    if (i >= j) return;
    const int r = root[i][j];
    out[r] = depth;
    bst_depths(root, i, r, depth + 1, out);
    bst_depths(root, r + 1, j, depth + 1, out);
}

inline long long cost_from_depths(const std::vector<long long>& f, const std::vector<int>& depth) {
    long long total = 0;
    for (std::size_t i = 0; i < f.size(); i++) total += f[i] * depth[i];
    return total;
}

inline std::string bst_shape(const SplitTable& root, const std::vector<std::string>& names, int i, int j) {
    if (i >= j) return "-";
    const int r = root[i][j];
    if (j - i == 1) return names[r];
    return names[r] + "(" + bst_shape(root, names, i, r) + " " + bst_shape(root, names, r + 1, j) + ")";
}

// Árbitro: genera todos los árboles del rango como listas de profundidades, y mide con la definición.
inline std::vector<std::vector<int>> all_bst_depths(int i, int j, int n) {
    if (i >= j) return {std::vector<int>(n, 0)};
    std::vector<std::vector<int>> trees;
    for (int r = i; r < j; r++) {
        for (const std::vector<int>& left : all_bst_depths(i, r, n)) {
            for (const std::vector<int>& right : all_bst_depths(r + 1, j, n)) {
                std::vector<int> depth(n, 0);
                depth[r] = 1;
                for (int x = i; x < r; x++) depth[x] = left[x] + 1;
                for (int x = r + 1; x < j; x++) depth[x] = right[x] + 1;
                trees.push_back(depth);
            }
        }
    }
    return trees;
}

inline long long bst_brute(const std::vector<long long>& f) {
    const int n = static_cast<int>(f.size());
    long long best = NO_COST;
    for (const std::vector<int>& depth : all_bst_depths(0, n, n)) {
        best = std::min(best, cost_from_depths(f, depth));
    }
    return best;
}

// Greedy que falla: la clave más frecuente a la raíz, y lo mismo en cada lado.
inline long long bst_most_frequent_root(const std::vector<long long>& f, int i, int j, int depth) {
    if (i >= j) return 0;
    int r = i;
    for (int x = i; x < j; x++) {
        if (f[x] > f[r]) r = x;
    }
    return f[r] * depth + bst_most_frequent_root(f, i, r, depth + 1) + bst_most_frequent_root(f, r + 1, j, depth + 1);
}

// La otra idea natural: el árbol balanceado, ignorando las frecuencias.
inline long long bst_balanced(const std::vector<long long>& f, int i, int j, int depth) {
    if (i >= j) return 0;
    const int r = i + (j - i) / 2;
    return f[r] * depth + bst_balanced(f, i, r, depth + 1) + bst_balanced(f, r + 1, j, depth + 1);
}