высшая проба отбор №2

/*Сдать решение задачи B-Бродячие музыканты
Полный балл:  100
Бонусные баллы:
Имя входного файла: in.txt или стандартный поток ввода
Имя выходного файла:   out.txt или стандартный поток вывода
Ограничение времени:  1 с
Ограничение памяти:    256M
Бродячие музыканты
Труппа бродячих музыкантов отправилась в путешествие из города 0 в город n+1. По дороге на равном расстоянии расположены n городов с номерами 1, 2, 3, ..., n, переход от одного городу к следующему занимает один день. В каждом городе музыканты могут выступить и получить прибыль (или убыток), равный ai марок для города i. Выступая в городе музыканты бесплатно пополняют запасы еды, однако не могут нести запас более чем на k дней пути.

В начале путешествия у музыкантов есть запас еды на k дней (то есть они могут дойти до городов с номерами от 1 до k не выступая в промежуточных городах) и p марок.

Определите максимальное количество марок, с которыми музыканты могут прийти в город n+1. Если в процессе выступлений у музыкантов не хватит денег чтобы оплатить убытки, то их путешествие закончится - в этом случае нужно вывести число -1.

Формат входных данных
В первой строке задано три целых неотрицательных числа n, k, p (1 ≤ k ≤ n ≤ 2 × 105, 0 ≤ p ≤ 109).

Во второй строке задано n целых чисел ai (-109 ≤ ai ≤ 109).

Формат результата
В единственной строке выведите ответ на задачу.

Примеры
Входные данные
3 1 0
-2 10 100
Результат работы
-1
Входные данные
3 1 2
-2 10 100
Результат работы
110
Входные данные
3 2 0
10 -3 7
Результат работы
17
Примечания
В первом примере музыканты имеют запас еды только на один день и 0 марок. Они обязаны выступить в первом городе и их денег не хватит для покрытия убытков.

Во втором примере музыканты также имеют запас еды только на один день и должны выступать в каждом городе, однако количество марок никогда не становится отрицательным.

В третьем примере музыканты выступают в городах 1 и 3.

Система оценки:

Решения, верно работающие при n ≤ 20 будут получать не менее 30 баллов.

Решения, верно работающие при n ≤ 1000 будут получать не менее 60 баллов.*/



#include<iostream>
#include<fstream>
#include<vector>
#include<stdint.h>
#include<algorithm>
#include<cmath>
#define all(container) container.begin(), container.end()
#define fors(counter, start, finish) for (int counter = start; counter < finish; ++counter)
#define forb(counter, start, finish) for (int counter = start; counter >= finish; --counter)
#define vec(type) std::vector<type>
#define dvec(type) std::vector<std::vector<type>>
//#define fin std::cin

struct town {
    int64_t p;
    int64_t k;
};

int64_t ans = -1, statk, n;
vec(int) a;
vec(town) point;

void travel(int t, int k, int64_t p) {
    if (point[t].p < p) {
        point[t].p = p;
        point[t].k = k;
    }
    if (p < 0 || point[t].k > k) {
        return;
    }
    else if (t == n) {
        ans = std::max(ans, p);
        return;
    }
    else {
        if (k > 0)
            travel(t + 1, k - 1, p);
        travel(t + 1, statk, p + a[t]);
    }
}

int main() {
    std::ifstream fin("in.txt");
    int64_t p, i = 0;
    fin >> n >> statk >> p;
    a.resize(n); point.resize(n + 1);
    fors(i, 0, n)
        fin >> a[i];
    travel(0, statk - 1, p);
    std::cout << ans;
    return 0;
}