Но учитывая, что все элементы уже упорядочены по своему индексу, много вычитаний делать не надо, можно просто один раз вычесть индекс первого элемента из остальных, и затем пробежаться по подмассиву, проверяя, превратились ли индексы в [1, 2, 3, ...]. Затем чекнуть сумму элементов, больше ли она, чем k. Все.

 >>/105736/
> Твое решение 0(n^2)
Вчера с колхоза приехал? Кружочек функции сложности это не ноль, а о-большое. И сложность решения с фильтрацией всего булеана будет не O(n^2), а O(2^n). Без дополнительных ограничений на устройство массива ее вряд ли можно уменьшить.