1. Идея

Нужно найти, сколько камней получит первый игрок, если оба играют оптимально.

В каждый момент игра определяется только одной вещью: с какой позиции начинается ещё не разобранный кусок массива. Потому что брать можно только с левого конца, значит после нескольких ходов остаётся просто суффикс массива.

Будем считать dp[i] — максимальное количество камней, которое сможет набрать игрок, делающий ход, если на столе остались кучки с номерами от i до n.

Тогда ответ — это dp[1].

Чтобы быстро понимать, сколько всего камней осталось в суффиксе, введём массив suf[i] — сумму a[i] + a[i+1] + ... + a[n].

Дальше используется очень удобная идея:

• если текущий игрок возьмёт одну или две кучки,
• то оставшиеся камни будут разыгрываться дальше,
• и следующий игрок на своём ходе сможет получить dp[...] камней из оставшегося суффикса,
• значит текущему игроку достанется все оставшиеся камни - то, что заберёт соперник.

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

Наблюдение 1. Состояние задаётся одной позицией

Так как брать можно только слева, после любого числа ходов остаются кучки i, i+1, ..., n для некоторого i.

Значит динамику можно строить по индексу i.

Наблюдение 2. Если взять одну кучку

Если текущий игрок из позиции i берёт только кучку i, то дальше игра продолжается с позиции i + 1.

В суффиксе i..n всего suf[i] камней.

Из оставшейся части i+1..n следующий игрок сможет набрать dp[i+1] камней.

Тогда текущий игрок суммарно получит:

a[i] + (остальные камни, которые не достанутся сопернику)

Но это удобно записать сразу так:

dp[i] = suf[i] - dp[i+1]

Почему? Потому что все камни суффикса i..n в итоге поделятся между двумя игроками, а соперник после нашего хода получит dp[i+1].

Наблюдение 3. Если взять две кучки

Если текущий игрок из позиции i берёт кучки i и i+1, то дальше остаётся суффикс с позиции i + 2.

Тогда он получит:

suf[i] - dp[i+2]

Наблюдение 4. Нужно взять лучший из двух вариантов

Значит переход такой:

• взять одну кучку: suf[i] - dp[i+1]
• взять две кучки: suf[i] - dp[i+2], если вторая кучка существует

Берём максимум.

3. Алгоритм

1. Считываем n и массив a.
2. Строим массив суффиксных сумм suf.
   • suf[i] = suf[i+1] + a[i]
3. Строим массив динамики dp с конца к началу.
   • сначала считаем вариант взять одну кучку: dp[i] = suf[i] - dp[i+1]
   • если i + 1 <= n, то можно взять две кучки: dp[i] = max(dp[i], suf[i] - dp[i+2])
4. Выводим dp[1].

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

Докажем по позициям с конца.

Рассмотрим состояние, когда на столе остались кучки i..n, и ходит некоторый игрок.

Обозначим через dp[i] максимальное число камней, которое он может получить при оптимальной игре дальше.

У текущего игрока есть не более двух допустимых ходов.

Случай 1. Взять одну кучку

Игрок забирает кучку i, после чего остаются кучки i+1..n, и ход переходит сопернику.

По определению dp[i+1] соперник сможет набрать из оставшегося суффикса максимум dp[i+1] камней.

Всего в суффиксе i..n находится suf[i] камней. Значит текущему игроку в итоге достанется всё остальное:

suf[i] - dp[i+1].

Случай 2. Взять две кучки

Если i+1 <= n, игрок может забрать кучки i и i+1. После этого остаются кучки i+2..n.

Аналогично, соперник потом сможет набрать dp[i+2] камней, значит текущий игрок получит:

suf[i] - dp[i+2].

Оптимальный выбор

Так как игрок играет оптимально, он выберет ход, который максимизирует его итоговый результат. Поэтому:

• если доступна только одна кучка, dp[i] = suf[i] - dp[i+1];
• если доступны две, то dp[i] = max(suf[i] - dp[i+1], suf[i] - dp[i+2]).

Именно это и считает алгоритм.

База

Когда кучек не осталось, игрок ничего взять не может, поэтому значения за пределами массива равны 0. Это естественно отражено в массивах dp и suf, где дополнительные элементы изначально нулевые.

Так как все переходы используют только уже посчитанные значения dp[i+1] и dp[i+2], вычисление с конца корректно.

Следовательно, dp[1] действительно равно числу камней, которое получит первый игрок.

5. Сложность

• Построение суффиксных сумм: O(n)
• Вычисление динамики: O(n)
• Общая сложность: O(n)
• Дополнительная память: O(n)

Из-за ограничения на сумму камней нужно использовать 64-битный целый тип:

• в C++ это long long
• в Python обычный int подходит автоматически

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<long long> suf(n + 3, 0), dp(n + 3, 0);

    for (int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] + a[i];
    }

    for (int i = n; i >= 1; i--) {
        dp[i] = suf[i] - dp[i + 1];
        if (i + 1 <= n) {
            dp[i] = max(dp[i], suf[i] - dp[i + 2]);
        }
    }

    cout << dp[1] << '\n';
    return 0;
}

7. Код на Python 3

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

a = [0] + a_list
suf = [0] * (n + 3)
dp = [0] * (n + 3)

for i in range(n, 0, -1):
    suf[i] = suf[i + 1] + a[i]

for i in range(n, 0, -1):
    dp[i] = suf[i] - dp[i + 1]
    if i + 1 <= n:
        dp[i] = max(dp[i], suf[i] - dp[i + 2])

print(dp[1])