Задача №115193. Большая хурма
Алиса и Боб купили большую хурму, разрезали её на \(n\) кусочков, размерами \(w_1, \dots, w_n\), и сразу начали её есть. Ребята будут есть кусочки одновременно, для каждого из них процесс поедания устроен следующим образом:
Как только кто-то закончил есть свой предыдущий кусочек (а также в самом начале трапезы), он выбирает очередной кусочек и начинает его есть. Если взять кусочек размером \(w\), то на его поедание уйдет ровно \(w\) секунд, а затем настанет время выбирать новый кусочек. Если оба одновременно закончили есть свой предыдущий кусочек (или если поедание только началось), то первой кусочек выбирает Алиса, но есть они начнут одновременно. Выбор нового кусочка не занимает времени.
Так как Алиса и Боб оба перфекционисты, когда они выбирают кусочек, то из всех оставшихся кусочков они возьмут либо самый маленький (с наименьшим \(w_i\)), либо самый большой (с наибольшим \(w_i\)).
Процесс поедания заканчивается, когда последний человек доел свой кусочек.
Алиса и Боб оба заинтересованы в том, чтобы съесть как можно больше хурмы. Найдите суммарный размер кусочков, которые съест Алиса, и которые съест Боб, если они оба будут выбирать кусочки оптимально.
В первой строке дано одно целое число \(n\) \((1 \le n \le 2000)\) — количество кусочков хурмы.
Во второй строке даны \(n\) целых чисел \(w_1,\ w_2,\ \dots,\ w_n\) (\(1 \le w_i \le 20\,000\), \(w_i \le w_{i + 1}\)) — размеры кусочков хурмы.
Обозначим за \(W\) сумму размеров всех кусочков. Гарантируется, что \(W \le 20\,000\).
В одной строке выведите два числа — суммарный размер всех кусочков, которые съест Алиса, и суммарный размер всех кусочков, которые съест Боб, если оба будут выбирать кусочки оптимально.
В первом примере Алисе стоит первым делом взять кусочек, размером \(1\). Сразу после этого Бобу тоже стоит взять кусочек размером \(1\). Спустя секунду, Алиса возмет кусочек размером \(3\), затем Боб возьмет кусочек размером \(6\). Ещё через \(3\) секунды Алиса возьмет кусочек размера \(4\). Ещё через \(3\) секунды Боб закончит есть, а ещё через секунду поедание закончится. При этом Алиса съест кусочки размерами \(1 + 3 + 4 = 8\), а Боб: \(1 + 6 = 7\)
В третьем примере Алисе стоит взять кусочек размером \(1\), а Бобу — размером \(7\). Через секунду Алиса возьмет себе кусочек размером \(9\), и ещё через \(6\) секунд, Боб возьмет себе кусочек, размером \(7\).
Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(w_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 10 | \(n = 3\) | – | – | – |
| 2 | 12 | – | \(w_i \le 2\) | – | – |
| 3 | 19 | \(n \le 200\) | \(w_i \le 500\) | 0 | – |
| 4 | 15 | \(n \le 500\) | \(W \le 5000\) | – | \(w_{i+1} \le 2 \cdot w_i\) для всех \(1 \le i \le n - 1\) |
| 5 | 13 | – | – | 2, 4 | \(w_{i+1} \le 2 \cdot w_i\) для всех \(1 \le i \le n - 1\) |
| 6 | 31 | – | – | 0 – 5 | Offline-проверка. |
5 1 1 3 4 6
8 7
4 1 1 2 2
3 3
4 1 7 7 9
10 14