Совсем скоро в продаже появится долгожданная игра Grand Theft Array V! Что, вы не слышали о ней?
Надо немедленно исправить это недоразумение!
Игровые действия в GTA V разворачиваются на одномерном массиве целых чисел. В игре участвуют два игрока, для каждого
из которых задана стартовая позиция. Игроки совершают ходы по очереди. На каждом ходу игрок забирает число,
написанное в его текущей ячейке, затем ставит туда ноль и переходит в смежную слева или справа
ячейку (разумеется, игрок не может выходить за пределы массива). Два игрока могут в некоторый момент времени
находиться в одной ячейке. Счёт игрока — это сумма всех набранных во время игры чисел. Игра заканчивается,
когда во всех ячейках массива записаны нули.
А теперь вычислите, какое максимальное количество очков могут набрать первый и второй игроки (первый игрок,
разумеется, ходит первым), если они играют оптимально, то есть стремятся максимизировать свой счёт, а если
существует несколько вариантов сделать это, то стараются минимизировать счёт противника.
Исходные данные
В первой строке записано целое число n — размер массива (10 ≤ n ≤ 105).
Во второй строке записаны n целых чисел — исходный массив.
Все элементы массива неотрицательны и не превосходят 10 000.
В третьей строке записаны два целых числа — стартовые позициии первого и второго игроков
соответственно. Индексация ячеек массива начинается с единицы.
Результат
Выведите два числа — счёт первого и второго игроков при оптимальной игре обоих.
Пример
исходные данные | результат |
---|
10
1 2 3 4 5 6 7 8 9 0
4 8
| 21 24
|
Автор задачи: Илья Кучумов (подготовка — Кирилл Девяткин)
Источник задачи: Уральская региональная командная олимпиада по программированию 2013