1. Идея

Нужно найти сумму всех элементов массива: даны n чеков, требуется посчитать общую выручку.

В условии упоминаются префиксные суммы: pre[i] — это сумма первых i элементов. Тогда ответ задачи — это pre[n], то есть сумма всех n чеков.

Но хранить весь массив префиксных сумм не нужно. Достаточно просто идти по элементам и поддерживать текущую сумму.

2. Наблюдения

• Ответ равен сумме всех чисел a_1 + a_2 + ... + a_n.
• Каждый новый чек просто добавляется к уже накопленной сумме.
• Из-за ограничений ответ может быть большим:
  • n до 2 * 10^5
  • каждый a_i по модулю до 10^9
• Поэтому в C++ нужен тип long long, а не int.

3. Алгоритм

1. Считать число n.
2. Завести переменную sum = 0.
3. n раз считать очередное число x и прибавлять его к sum.
4. Вывести sum.

4. Почему это работает

После чтения первого элемента sum равна сумме первого чека.

После чтения второго элемента sum равна сумме первых двух чеков.

И так далее: после чтения i элементов переменная sum хранит сумму этих i элементов, то есть текущую префиксную сумму.

Значит, после обработки всех n чисел переменная sum будет равна pre[n], а именно это и требуется вывести.

5. Сложность

• Время: O(n), потому что каждый элемент обрабатывается ровно один раз.
• Память:
  • для решения на C++: O(1), так как храним только текущую сумму и очередное число;
  • для приведённого решения на Python: O(n), потому что сначала считывается список всех чисел.

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long sum = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        sum += x;
    }

    cout << sum << "\n";
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

s = 0
for x in a:
    s += x

print(s)