Клиппи и Мерлин грабят банк. Клиппи и Мерлин решили грабить банк, который представляет собой N расположенных в ряд банковских ячеек, пронумерованных последовательно числами от 1 до N. С помощью своего друга Ровера, который работал в банке сторожевым псом, они добыли ключи от всех ячеек, а также узнали, как много ценностей хранится в каждой ячейке. Чтобы не вызывать лишних подозрений, Клиппи и Мерлин решили ограбить всего две ячейки — по одной на каждого. Также, чтобы охрана банка не почуяла неладного, они решили работать далеко друг от друга — между ними должно быть не меньше K банковских ячеек. Входные данные: В первой строке вводятся два числа — N (2 ≤ N ≤ 10^5) и K (0 ≤ K < N). Выходные данные: Выведите два числа в возрастающем порядке — номера ячеек, которые нужно ограбить, чтобы суммарно украсть как можно более дорогие ценности, не вызвав при этом лишних подозрений. Если вариантов несколько, выберите тот, в котором меньший номер вскрываемой ячейки был бы как можно ближе к единице. Если и таких вариантов несколько, выберите тот, в котором и больший номер вскрываемой ячейки был бы как можно меньше. Примеры: Ввод: 6 2 2 4 3 1 4 4 Вывод: 2 5

Идея решения

Нужно выбрать две ячейки i и j (i < j), причём между ними должно быть как минимум K ячеек:

или:

Если перебирать правую ячейку j, то для неё нужно знать самую ценную из всех допустимых левых ячеек. Достаточно идти слева направо и поддерживать лучшую ячейку, которая уже может быть парой для текущей j.

При выборе лучшей левой ячейки учитываем:

1. большее количество ценностей;

2. если ценности равны — меньший номер ячейки.

При выборе ответа учитываем:

1. максимальную сумму;

2. если суммы равны — минимальный номер первой ячейки;

3. если и он равен — минимальный номер второй ячейки.

Сложность: O(N) по времени и O(N) по памяти (можно сделать и O(1), но массив нужен для чтения).

Решение на C++17

C++
#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    vector<long long> a(N + 1);
    for (int i = 1; i <= N; i++)
        cin >> a[i];
    long long bestLeftValue = -1;
    int bestLeft = -1;
    long long ansSum = -1;
    int ansI = -1, ansJ = -1;
    for (int j = 1; j <= N; j++) {
        int canBeLeft = j - K - 1;
        if (canBeLeft >= 1) {
            if (a[canBeLeft] > bestLeftValue ||
                (a[canBeLeft] == bestLeftValue && canBeLeft < bestLeft)) {
                bestLeftValue = a[canBeLeft];
                bestLeft = canBeLeft;
            }
        }
        if (bestLeft != -1) {
            long long sum = bestLeftValue + a[j];
            if (sum > ansSum ||
                (sum == ansSum && bestLeft < ansI) ||
                (sum == ansSum && bestLeft == ansI && j < ansJ)) {
                ansSum = sum;
                ansI = bestLeft;
                ansJ = j;
            }
        }
    }
    cout << ansI << ' ' << ansJ << '\n';
    return 0;
}