Информатика 10 класс

Надеюсь, тебе нужно было на Питоне. Вот код:

 from math import isqrt



# Количество сокровищ, которое можно украсть из залов, содержащих a[...] сокровищ,

# если к первому залу есть фора в adv минут

def maxloot(a, adv):

    if not a: return 0

    # Наименьшее целое не менее положительного корня уравнения (m² + m) / 2 = a₀.

    # Столько минут вор может провести в первом зале с пользой. 

    maxtime = isqrt(2 * a[0])

    # Пробуем каждое целесообразное количество минут и делегируем остаток следующим залам.

    return max(min(m * (m + 1) // 2, a[0]) + maxloot(a[1:], adv - m + 1)

        for m in range(min(maxtime, adv) + 1))



t = int(input())

print('\n'.join(str(maxloot(a, 1)) for _ in range(t)

    for a in (input(), [int(s) for s in input().split()])[1:])) 

Не знаю, насколько тут нужны пояснения.
Функция maxloot вычисляет максимально возможную добычу для последовательности залов с заданным количеством сокровищ внутри и для заданной форы.
Для первого зала она находит максимальное количество минут (maxtime), требуемое для приватизации всего содержимого зала. Учитывая, что за m минут можно приватизировать m(m+1)/2 сокровищ (сумма прогрессии), количество минут для приватизации a₀ - это положительное решение квадратного уравнения относительно m. Округлять его надо, естественно, вверх.
Далее функция рассчитывает все варианты добычи от 0 до макс. количества минут, но не более имеющейся форы, и берёт максимум из всех вариантов. Один вариант добычи при m минутах в первом зале - это m(m + 1)/2 в первом зале (но не более имеющегося там количества сокровищ) и maxloot для остатка залов с делегированием им оставшегося времени + 1 (при переходе в зал добавляется фора в 1 минуту).

А основной код считает добычу отдельно для каждого тест кейса и выводит результаты.

Сложность алгоритма: O(t * ΣΠ(min(aᵣᵢ, i))), где Π - произведение по всем i от 0 до nᵣ, а Σ - сумма по всем r от 0 до t. Можно сказать, что сложность ограничена факториалом от максимального количества залов в тест кейсах, т.е. зависит от него экспоненциально.

Например, если ввести в качестве последовательности aᵢ числа от 1 до 30, алгоритм работает заметно долго. Если понадобится обрабатывать последовательности такой длины, то можно посмотреть в сторону динамического программирования или кэширования результатов, т.к. maxloot многократно вызывается с одними и теми же параметрами, а её результат зависит только от значений этих параметров.

 from math import isqrt



CACHE = {}

def cached(f, *args):

    global CACHE

    k = tuple(args)

    if k not in CACHE: CACHE[k] = f(*args)

    return CACHE[k]



def maxloot(a, adv):

    if not a: return 0

    maxtime = isqrt(2 * a[0])

    return max(min(m * (m + 1) // 2, a[0]) + cached(maxloot, a[1:], adv - m + 1)

        for m in range(min(maxtime, adv) + 1))



t = int(input())

print('\n'.join(str(maxloot(a, 1)) for _ in range(t)

    for a in (input(), tuple(int(s) for s in input().split()))[1:]))