1411 . Ragnarök
TopCoder
Tags
Description
諸神的黃昏（Ragnarök）是北歐神話的預言中註定要降臨的末日劫難，也是日爾曼民族的神話與其他民族神話最富悲劇特色的區別。
不同其他神話傳說用大篇幅敘述神對世界的創造，北歐神話用最濃重的筆墨描繪了包括諸神在內都必須面對的宇宙毀滅。
經過研究你得知還是有解決的辦法！那就是維護天神間的平衡。
北歐諸神神座的位置相當有趣，是呈一條長鏈狀。
諸神又分為三種：天神、冥神以及土地神。
而諸神的黃昏則是因為天神與冥神之間的數量不平衡所引發。
你發現最後的方法就是保留某區段的神明，使其區段保持平衡，但相對的必須捨棄掉剩下的那些神明。
又因為能量的關係，你最多只能保留一區段的神明。
現在諸神的黃昏來了！你最多能拯救多少神明呢？
Input Format
本題有多筆測試資料，請以 EOF 作為結束
每筆資料的：
第一行有一個整數 $n$，代表有多少神明（$0 \le n \le 10 ^ 6$）
接下來有 $n$ 行，每行有一個整數 $s_i$ 代表諸神的分類（正數為天神、負數為冥神、$0$ 則是土地神），$-2 ^ {31} < s_i < 2 ^ {31}$
Output Format
對於每筆資料輸出一個整數 $p$，代表最多能保護 $p$ 位神明
Sample Input 1
5
1
-1
-1
0
1
1
-1
-1
0
1
Sample Output 1
5
Hints
※2008/07/27 範圍敘述修正 by ggm
※2008/07/27 題目敘述修正 by hallogameboy , 感謝 SKYLY
Problem Source
原TIOJ1411 / 快樂暑假營複習賽。Problem Setter：hallogameboy
2021.03.26 Update: Added $\LaTeX$ by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 50 |
| 2 | 1 | 50 |