| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Одна из популярных настольных игр <<Эй! Это МОЯ рыба!>> состоит в перемещении пингвинов и сбору рыбы на поле.
Мы рассмотрим упрощенную версию этой игры. Для этой игры используется $n$ карточек с изображениями нескольких рыб и фишки-пингвины.
В начале игры карточки выкладываются на столе в ряд в некотором порядке.
Каждому игроку выдается по два пингвина. Затем первый игрок размещает одного из своих пингвинов на незанятой льдине. После этого второй игрок делает то же самое. После этого они аналогично размещают своих вторых пингвинов.
Как только все пингвины находятся на льдинах, лов рыбы начинается! Игроки ходят по очереди. Ход состоит из перемещения одного из пингвинов текущего игрока, после этого игрок берет льдину --- карточку, на которой его пингвин стоял в начале его хода, и кладет ее перед собой.
Пингвин может двигаться по льдинам любом направлении и остановиться на любой незанятой льдине. При этом запрещено перепрыгивать через других пингвинов и через проруби, оставшиеся после удаления льдин. Если у пингвина с обеих сторон препятствие, то он не может двигаться.
Если игрок не может переместить ни одного из его пингвинов, он забирает всех своих пингвинов и льдины, на которых эти пингвины стояли. После этого второй игрок продолжает делать ходы, пока он может перемещать своих пингвинов.
В конце игры каждый игрок считает количество рыб на всех собранных им карточках. Цель игрока максимизировать разность своего количества рыб и количества рыб противника. Какую максимальную разность может получить первый игрок, при оптимальной игре второго игрока.
В первой строке входного файла число $n$ (4ドル \le n \le 10$) --- количество карточек. Во второй строке файла находится $n$ чисел $a_i$ --- количество рыб на карточках в порядке в котором они выложены на столе. 1ドル \le a_i \le 10^6$.
В выходной файл выведите одно число: какую максимальную разность может получить первый игрок, при оптимальной игре второго игрока.
7 1 3 2 2 3 2 1
0
Пример игры для теста из условия
В начале игры на поле нет ни одного пингвина:
Первый игрок выставляет первого пингвина:
Второй игрок выставляет первого пингвина:
Первый игрок выставляет своего второго пингвина:
Второй игрок выставляет своего второго пингвина:
Ход первого игрока:
Ход второго игрока:
Ход первого игрока: