Как оптимизировать задачу по времени?

Есть код

n, m = map(int, input('').split())
grades = list(map(int, input().split()))


def calculate(m, grades):
    result = 0

    for i in range(m):
        if grades[i] != 0:
            result += grades[i]**2
            counter = 0
            for j in range(i + 1, m):
                if counter == grades[i]:
                    break
                if grades[j] != 0:
                    result += grades[j]
                    counter += 1
        return result


print(calculate(m, grades))

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


Ответы (1 шт):

Автор решения: MBo

Создайте дополнительный список, в который собирайте кумулятивные (накопленные) суммы ненулевых оценок. Например, для gr = [1,0,2,0,0,3,0,4] это будет cs = [1,3,6,10].

Чтобы найти частичную сумму по ячейкам с а по b включительно, нужно вычесть cs[b]-cs[a-1].

Списки обходить с конца, индекс в cs уменьшается, когда ненулевое значение в gr.

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

→ Ссылка