Ограничение времени 2 секунды Ограничение памяти 2...

cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

static const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    int L;
    cin >> N >> M >> L;

    vector<int> X(N);
    for (int i = 0; i < N; ++i) cin >> X[i];

    struct Query {
        int a, b, r, k;
    };
    vector<Query> queries(M);
    for (int i = 0; i < M; ++i) {
        cin >> queries[i].a >> queries[i].b >> queries[i].r >> queries[i].k;
        --queries[i].a;
        --queries[i].b;
    }

    // Сортируем города по положению на кольце.
    vector<pair<int,int>> ord;
    ord.reserve(N);
    for (int i = 0; i < N; ++i) ord.push_back({X[i], i});
    sort(ord.begin(), ord.end());

    vector<int> pos(N);          // позиции в отсортированном порядке
    vector<int> sortedId(N);     // какой исходный id стоит на этой позиции
    vector<int> placeOfId(N);    // где находится исходный id в отсортированном порядке
    for (int i = 0; i < N; ++i) {
        pos[i] = ord[i].first;
        sortedId[i] = ord[i].second;
        placeOfId[ord[i].second] = i;
    }

    // bestCW[s][e][k] = минимально возможная максимальная длина одного прыжка
    // на дуге по часовой стрелке от s до e, если разрешено не более k ретрансляторов.
    // Храним в одном массиве.
    int KMAX = N;
    size_t SZ = (size_t)N * N * (KMAX + 1);
    vector<int> bestCW(SZ, INF);

    auto idx = [N, KMAX](int s, int e, int k) -> size_t {
        return ((size_t)s * N + e) * (KMAX + 1) + k;
    };

    // Для каждой стартовой вершины считаем DP на линейной развертке по часовой стрелке.
    for (int s = 0; s < N; ++s) {
        vector<int> y(N); // y[j] = расстояние от s до (s+j) по часовой стрелке, y[0]=0
        y[0] = 0;
        for (int j = 1; j < N; ++j) {
            int to = (s + j) % N;
            y[j] = (to >= s ? pos[to] - pos[s] : L - pos[s] + pos[to]);
        }

        vector<int> prev(N, INF), cur(N, INF);
        prev[0] = 0;

        // seg = число отрезков, relays = seg - 1
        for (int seg = 1; seg <= N - 1; ++seg) {
            fill(cur.begin(), cur.end(), INF);

            int ptr = seg - 1; // допустимый минимум для последней точки разбиения

            for (int j = seg; j <= N - 1; ++j) {
                auto cost = [&](int t) -> int {
                    return max(prev[t], y[j] - y[t]);
                };

                while (ptr + 1 < j && cost(ptr + 1) <= cost(ptr)) {
                    ++ptr;
                }

                cur[j] = cost(ptr);

                int e = (s + j) % N;
                int relays = seg - 1;
                bestCW[idx(s, e, relays)] = cur[j];
            }

            prev.swap(cur);
        }

        // Если ретрансляторов больше, чем промежуточных городов на дуге,
        // ответ уже не улучшается.
        for (int j = 1; j <= N - 1; ++j) {
            int e = (s + j) % N;
            int maxUseful = j - 1;
            int val = bestCW[idx(s, e, maxUseful)];
            for (int k = maxUseful + 1; k <= N; ++k) {
                bestCW[idx(s, e, k)] = val;
            }
        }
    }

    auto cwDist = [&](int s, int e) -> int {
        if (e >= s) return pos[e] - pos[s];
        return L - pos[s] + pos[e];
    };

    ll answer = 0;

    for (const auto &q : queries) {
        int u = placeOfId[q.a];
        int v = placeOfId[q.b];

        int dCW = cwDist(u, v);
        int dCCW = L - dCW;

        ll need;

        if (dCW < dCCW) {
            int step = (v - u + N) % N;          // число дуг между соседями на дуге CW
            int k = min(q.k, step - 1);
            need = 1LL * bestCW[idx(u, v, k)] * q.r;
        } else if (dCCW < dCW) {
            int step = (u - v + N) % N;          // CW от v до u = CCW от u до v
            int k = min(q.k, step - 1);
            need = 1LL * bestCW[idx(v, u, k)] * q.r;
        } else {
            // Если обе полуокружности одинаковы, можно выбрать лучшую из двух.
            int step1 = (v - u + N) % N;
            int k1 = min(q.k, step1 - 1);
            ll need1 = 1LL * bestCW[idx(u, v, k1)] * q.r;

            int step2 = (u - v + N) % N;
            int k2 = min(q.k, step2 - 1);
            ll need2 = 1LL * bestCW[idx(v, u, k2)] * q.r;

            need = min(need1, need2);
        }

        answer = max(answer, need);
    }

    cout << answer << '\n';
    return 0;
}

Идея

Для одной линии фиксированы:

• дуга кольца между двумя городами,
• коэффициент затухания R,
• не более K ретрансляторов.

Если на этой дуге выбрать несколько промежуточных городов, то сигнал идёт прыжками между соседними выбранными точками.
Для мощности P каждый прыжок длины d возможен тогда и только тогда, когда P >= d * R.

Значит для линии надо минимизировать максимальную длину одного прыжка на нужной дуге, используя не более K ретрансляторов.
Тогда требуемая мощность для линии равна:

$$(\text{минимально возможный максимум прыжка}) \cdot R$$

Общий ответ — максимум по всем линиям.

---

Как считать быстро

Города сортируются по координате на кольце.
Для каждой стартовой точки s рассматриваем все города по часовой стрелке как линейную последовательность.

Пусть:

• y[j] — расстояние от s до j-го города по часовой стрелке,
• dp[t][j] — минимально возможный максимум прыжка, если дойти до j за t отрезков связи.

Переход:

$$dp[t][j] = \min_{p < j} \max(dp[t-1][p],\ y[j]-y[p])$$

Здесь p — последняя точка, где стоит ретранслятор.

Так как:

• dp[t-1][p] не убывает по p,
• y[j]-y[p] не возрастает по p,

оптимальный p двигается только вправо, поэтому переходы для фиксированного t можно считать двумя указателями за O(N).

Итого:

• предвычисление: O(N^3),
• ответы на M запросов: O(M).

При N <= 300, M <= 1e5 это проходит с большим запасом.

Если хочешь, я могу ещё отдельно расписать доказательство корректности этого DP.