Codeforces Round 550 (Div. 3) |
---|
Закончено |
У Поликарпа есть массив $$$a$$$, состоящий из $$$n$$$ целых чисел.
Он хочет поиграть в игру с этим массивом. Игра состоит из нескольких шагов. Во время первого хода он выбирает любой элемент и удаляет его (после первого хода массив содержит $$$n-1$$$ элемент). Для каждого из следующих ходов он выбирает любой элемент с одним ограничением: его четность должна отличаться от четности элемента, удаленного во время прошлого хода. Другими словами, он меняет четности (четный-нечетный-четный-нечетный-... или нечетный-четный-нечетный-четный-...) удаляемых элементов. Поликарп останавливается, если не может совершить ход.
Формально:
Цель Поликарпа — минимизировать сумму неудаленных элементов массива после конца игры. Если Поликарп может удалить массив целиком, тогда сумма неудаленных элементов равна нулю.
Помогите Поликарпу найти это значение.
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2000$$$) — количество элементов в $$$a$$$.
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^6$$$), где $$$a_i$$$ — $$$i$$$-й элемент $$$a$$$.
Выведите одно целое число — минимально возможную сумму неудаленных элементов массива после конца игры.
5 1 5 7 8 2
0
6 5 1 2 4 6 3
0
2 1000000 1000000
1000000
Название |
---|