Задача Джерримендеринг

Сдать решение задачи 5-Джерримендеринг
Полный балл: 100
Ограничение времени: 1 с
Ограничение памяти: 512M
Ограничение размера стека: 64M
Задача 5: Джерримендеринг
Джерримендеринг — разделение территории на избирательные округа неестественным образом с целью искусственного изменения соотношения политических сил в них и, как следствие, в целом на территории проведения выборов. Например, при необходимости обеспечить победу на территории партии X (если от одного избирательного округа избирается один кандидат или один выборщик), нужно всех противников X сосредоточить по округам, где X не сможет выиграть, а всех сторонников X распределить так, чтобы они обеспечивали уверенную победу с небольшим перевесом в нужных округах. Например, в тесте из условия всего за X голосует 10 человек, а против X голосует 15 человек, но, благодаря специальному разделению по округам, X выигрывает в двух избирательных округах из трёх.

В этой задаче избирательная территория представляет собой улицу, на которой в ряд расположены N домов. В i-м доме проживает ai человек, и все они голосуют одинаково: либо за партию X, либо за другую партию. Улицу необходимо разбить на три избирательных округа, от каждого избирательного округа будет избираться один кандидат, и необходимо произвести такую нарезку улицы на три избирательных округа, чтобы минимум в двух округах из трёх выиграл кандидат от партии X. Кандидат от партии X выигрывает, если за него голосует более половины избирателей, проживающих в домах данного избирательного округа. Но чтобы вас не заподозрили в джерримендеринге, необходимо, чтобы каждый избирательный округ представлял собой непрерывный отрезок из номеров домов, то есть сначала вдоль по улице идут дома первого избирательного округа, затем — второго, затем — третьего. Каждый избирательный округ должен содержать как минимум один дом.

Входные данные
Первая строка входных данных содержит целое число N (3 ≤ N ≤ 105) — количество домов на улице. Следующие N строк содержат по одному целому числу ai (0 < |ai| ≤ 104). Если ai > 0, то в i-м доме проживает ai избирателей, голосующих за кандидата от партии X. Если ai < 0, то в i-м доме проживает |ai| избирателей, голосующих против кандидата от партии X.

Выходные данные
Если возможно разделить N домов на три округа так, что минимум в двух округах выигрывает кандидат от партии X, программа должна вывести три целых положительных числа N1, N2, N3, N1 + N2 + N3 = N, соответствующих количеству домов в первом, втором и третьем избирательном округе от начала улицы. При таком разбиении минимум в двух округах из трёх должен выигрывать кандидат от партии X. Если возможно несколько таких разбиений, необходимо вывести любое из них.

Если искомое разбиение не существует, программа должна вывести одно число 0.

Система оценивания
Решения, правильно работающие при N ≤ 100, будут оцениваться в 40 баллов.

Решения, правильно работающие при N ≤ 1000, будут оцениваться в 70 баллов.

Пример
Ввод
7
-3
-5
3
-4
2
5
-3

Вывод
4 1 2

Пояснение
На улице расположены 7 домов, избиратели в них распределены так: (−3, −5, 3, −4, 2, 5, −3). Правильный ответ: 4, 1, 2. При таком разбиении в первом округе оказываются 4 дома: (−3, −5, 3, −4). В этом округе за X голосует 3 избирателя, против — 12 избирателей и X разгромно проигрывает. В следующем округе один дом, в котором 2 избирателя голосуют за X, в этом округе X выиграет. В третьем округе два дома: (5, −3), и в этом округе X тоже выиграет. Итого X выигрывает в двух округах.

0