TopCoder

Thumb 48201280 p0
Sylveon
仙子精靈的身體以白色為主。它的耳朵、尾巴、腿的下半部分是粉色,耳朵裡是藍色。頭頂和脖子上有觸角,兩對觸角中間都有一個蝴蝶結。AC的都是水題

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

44.9% (22/49)

Description

諸神的黃昏(Ragnarök)是北歐神話的預言中註定要降臨的末日劫難,也是日爾曼民族的神話與其他民族神話最富悲劇特色的區別。

不同其他神話傳說用大篇幅敘述神對世界的創造,北歐神話用最濃重的筆墨描繪了包括諸神在內都必須面對的宇宙毀滅。

經過研究你得知還是有解決的辦法!那就是維護天神間的平衡。

北歐諸神神座的位置相當有趣,是呈一條長鏈狀。

諸神又分為三種:天神、冥神以及土地神。

而諸神的黃昏則是因為天神與冥神之間的數量不平衡所引發。

你發現最後的方法就是保留某區段的神明,使其區段保持平衡,但相對的必須捨棄掉剩下的那些神明。

又因為能量的關係,你最多只能保留一區段的神明。

現在諸神的黃昏來了!你最多能拯救多少神明呢?

Input Format

本題有多筆測試資料,請以EOF作為結束

每筆資料的:

第一行有一個整數n,代表有多少神明 (0<=n<=1,000,000)

接下來有n行,每行有一個整數si代表諸神的分類(正數為天神、負數為冥神、0則是土地神)
(-231 < si < 231)

Output Format

對於每筆資料輸出一個整數p,代表最多能保護p位神明

Sample Input

5
1
-1
-1
0
1

Sample Output

5

Hints

※2008/07/27 範圍敘述修正 by ggm
※2008/07/27 題目敘述修正 by hallogameboy , 感謝 SKYLY

Problem Source

原TIOJ1411 / 快樂暑假營複習賽。Problem Setter:hallogameboy

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 65536
1 5000 65536 65536