1. Идея

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

В таких играх удобно считать не сами суммы игроков по отдельности, а разность:

• счёт текущего игрока - счёт соперника

для некоторого подотрезка жетонов.

Тогда задача сводится к следующему:

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

Именно эта идея используется в эталонном решении.

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

Наблюдение 1. Что хранить в динамике

Рассмотрим отрезок жетонов a[l...r].

Пусть значение состояния — это максимальная разность очков:

(очки текущего игрока) - (очки другого игрока)

которую можно получить на этом отрезке при оптимальной игре обоих.

Обозначим это как f(l, r).

Если на отрезке остался один жетон, то всё просто:

• игрок берёт его и получает разность a[l].

То есть:

• f(l, l) = a[l]

Наблюдение 2. Переход

Если игрок берёт левый жетон a[l], то дальше соперник будет играть первым на отрезке l+1...r.

Но f(l+1, r) — это разность в пользу того игрока, который ходит на этом новом отрезке, то есть в пользу соперника.

Значит, для текущего игрока итоговая разность после взятия левого жетона будет:

• a[l] - f(l+1, r)

Аналогично, если взять правый жетон:

• a[r] - f(l, r-1)

Текущий игрок выбирает лучший вариант:

• f(l, r) = max(a[l] - f(l+1, r), a[r] - f(l, r-1))

Наблюдение 3. Что означает ответ

Для всего массива нас интересует f(0, n-1).

• Если f(0, n-1) >= 0, то первый игрок может закончить игру с не меньшим счётом, чем второй.
• Иначе он проигрывает при оптимальной игре.

Значит:

• если итоговая разность неотрицательна, выводим WIN;
• иначе выводим LOSE.

3. Алгоритм

Эталонное решение делает динамику по длине отрезка и использует одномерный массив.

Что хранится в dp

Изначально:

• dp[l] = a[l]

Это соответствует отрезкам длины 1.

Далее будем увеличивать длину отрезка от 2 до n.

Для фиксированной длины len и левой границы l:

• r = l + len - 1

Тогда:

• dp[l + 1] в этот момент хранит значение для отрезка l+1...r
• dp[l] до перезаписи хранит значение для отрезка l...r-1

Поэтому можно посчитать:

• takeLeft = a[l] - dp[l + 1]
• takeRight = a[r] - dp[l]
• dp[l] = max(takeLeft, takeRight)

После завершения всех переходов:

• dp[0] — это ответ для всего массива.

Пошагово

1. Считать n и массив a.
2. Создать массив dp, изначально равный a.
3. Для len от 2 до n:
   • для всех допустимых l:
     • r = l + len - 1
     • вычислить два варианта: взять левый или правый жетон;
     • записать максимум в dp[l].
4. Если dp[0] >= 0, вывести WIN, иначе LOSE.

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

Докажем корректность динамики.

База

Для отрезка длины 1, то есть l = r, игрок может взять только этот жетон.

Тогда его итоговое преимущество над соперником равно a[l].

Значит, базовое значение:

• f(l, l) = a[l]

совершенно верно.

Переход

Предположим, что для всех отрезков меньшей длины значения динамики посчитаны правильно.

Рассмотрим отрезок a[l...r].

Текущий игрок имеет два возможных хода.

Вариант 1: взять левый жетон

Игрок получает a[l].

После этого остаётся отрезок a[l+1...r], и теперь уже соперник ходит первым на этом отрезке.

По определению f(l+1, r) — это максимальная разность:

• (очки соперника) - (очки текущего игрока на оставшемся отрезке)

Значит, с точки зрения текущего игрока итоговая разность будет:

• a[l] - f(l+1, r)

Вариант 2: взять правый жетон

Аналогично получаем:

• a[r] - f(l, r-1)

Выбор лучшего действия

Игрок играет оптимально, значит выбирает ход, дающий максимальную итоговую разность.

Поэтому:

• f(l, r) = max(a[l] - f(l+1, r), a[r] - f(l, r-1))

Это и есть используемый переход.

Почему достаточно проверить знак f(0, n-1)

f(0, n-1) — это разность:

• (очки первого игрока) - (очки второго игрока)

при оптимальной игре с самого начала.

Если она неотрицательна, то первый игрок гарантирует результат не хуже ничьей, а по условию это означает WIN.

Если она отрицательна, то второй игрок сможет набрать строго больше, значит ответ LOSE.

Следовательно, алгоритм корректен.

5. Сложность

Перебираются все длины отрезков от 1 до n, а для каждой длины — все возможные левые границы.

Итого:

• время: O(n^2)
• память: O(n)

При n <= 2000 это легко проходит.

6. Код на C++17

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

using namespace std;

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

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

    vector<long long> dp = a;

    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            long long takeLeft = a[l] - dp[l + 1];
            long long takeRight = a[r] - dp[l];
            dp[l] = max(takeLeft, takeRight);
        }
    }

    if (dp[0] >= 0) {
        cout << "WIN\n";
    } else {
        cout << "LOSE\n";
    }

    return 0;
}

7. Код на Python 3

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

dp = a[:]

for length in range(2, n + 1):
    for l in range(0, n - length + 1):
        r = l + length - 1
        take_left = a[l] - dp[l + 1]
        take_right = a[r] - dp[l]
        dp[l] = max(take_left, take_right)

if dp[0] >= 0:
    print("WIN")
else:
    print("LOSE")