. Джерримендеринг Ограничение времени 1 секунда
Ограничение памяти 512Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Джерримендеринг — разделение территории на избирательные округа неестественным образом с целью искусственного изменения соотношения политических сил в них и, как следствие, в целом на территории проведения выборов. Например, при необходимости обеспечить победу на территории партии X (если от одного избирательного округа избирается один кандидат или один выборщик), нужно всех противников X сосредоточить по округам, где X не сможет выиграть, а всех сторонников X распределить так, чтобы они обеспечивали уверенную победу с небольшим перевесом в нужных округах. Например, в тесте из условия всего за X голосует 10 человек, а против X голосует 15 человек, но, благодаря специальному разделению по округам, X выигрывает в двух избирательных округах из трёх.
В этой задаче избирательная территория представляет собой улицу, на которой в ряд расположены N домов. В i-м доме проживает ai человек, и все они голосуют одинаково: либо за партию X, либо за другую партию. Улицу необходимо разбить на три избирательных округа, от каждого избирательного округа будет избираться один кандидат, и необходимо произвести такую нарезку улицы на три избирательных округа, чтобы минимум в двух округах из трёх выиграл кандидат от партии X. Кандидат от партии X выигрывает, если за него голосует более половины избирателей, проживающих в домах данного избирательного округа. Но чтобы вас не заподозрили в джерримендеринге, необходимо, чтобы каждый избирательный округ представлял собой непрерывный отрезок из номеров домов, то есть сначала вдоль по улице идут дома первого избирательного округа, затем — второго, затем — третьего. Каждый избирательный округ должен содержать как минимум один дом.
Формат ввода
Первая строка входных данных содержит целое число N (3≤ N≤ 105) — количество домов на улице. Следующие N строк содержат по одному целому числу ai (0 0, то в i-м доме проживает ai избирателей, голосующих за кандидата от партии X. Если ai<0, то в i-м доме проживает |ai| избирателей, голосующих против кандидата от партии X.
Формат вывода
Если возможно разделить N домов на три округа так, что минимум в двух округах выигрывает кандидат от партии X, программа должна вывести три целых положительных числа N1, N2, N3, N1+N2+N3=N, соответствующих количеству домов в первом, втором и третьем избирательном округе от начала улицы. При таком разбиении минимум в двух округах из трёх должен выигрывать кандидат от партии X. Если возможно несколько таких разбиений, необходимо вывести любое из них.
Если искомое разбиение не существует, программа должна вывести одно число 0.
Пример
Ввод Вывод
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 выигрывает в двух округах.
Решения, правильно работающие при N≤ 100, будут оцениваться в
Решения, правильно работающие при N≤ 1000, будут оцениваться в
решить задачу олимпиада по информатике
