Как оптимизировать задачу по времени?
Есть код
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.
В принципе, исходный список можно сжать, удалив нули, но радикально это ничего не улучшит, т.к. решение и так получится линейным