TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

21.6% (11/51)

Description

這題的題目是要你輸出或是計算後輸出一些答案。
以下是題目敘述,如果你很趕時間最好可以直接跳過去看輸入說明。


你聽過誠哥的故事嗎?那是一個真實、感人、卻又反映出人性黑暗的故事。

就算你沒聽過,你也知道甚麼是「編譯器」,那個人,對,就是瑞南,那個曾經試圖想要自己改寫一個不會編譯錯誤的編譯器,這就是他被朋友阻止後的故事。

事情的發生要從大黑魔導士「諳(ㄢ)慄(ㄌㄧˋ)」(ALT)說起,不過這題空間可能不夠,畢竟隨便一個黑魔法都需要三十頁的論文來討論,只為了證明他自己很難用,我們就先從<周強.h>的作者,沒錯,就是周強開始說起。
話說當年周強還是少年的時候,曾在一個東方盡頭的一個小島上,得到特級摳德(coder)的稱號。在此之前,南天門大師兄上級國家平衡樹摳得日月卦長,曾經上門和他討論關於黯黑摳頂界愈來愈胖的消息和對策。
「你會喝金門高粱嗎?」卦長一上門就這樣質問周強。
「你這是悖論(ㄅㄛˊㄌㄨㄣˋ)。」周強一語驚醒夢中人,卦長覺得情況不對,使出「萬國驚天掌」,但是對於有#include <周強.h>的周強,就像是打模擬賽一樣,輕鬆就破解(台)了。
「你怎麼帥成這樣?」在經歷了線段流(segment flow)和執行時間陣列(runtime array),卦長終於承受不住O(n)的<周強.h>。
「要不是需要輸出,我就有O(1)了。」周強說。
「這,難道是黑魔法。」卦長嚥下最後一口氣睡著前,口中說出了他心中的疑問。
「不,<周強.h>不是區區可以比擬的。」聽到這句話,卦長開悟了,日後寫出傻B樹也是之後的故事了。

瑞南,從「好,船」(Nice,boat)上得到了編譯器的資料,隨著海流飄到了東方的小島,正好目睹了這一幕。
「這,難道就是那個傳說嗎!只要得到傳說中的<周強.h>,並透過傳說中的編譯器編譯,就可以寫出長生不老的資料結構。」瑞南踏上了尋找傳說中的編譯器的旅程,因為他知道,胖,就是找到編譯器的唯一正義。

同時,大黑魔導士「諳慄」(ALT)用O(n)查詢size()的std::list<周強>看著這一切,一邊在FB上說別人胖。CBD看不下去了,從第3世界的POI離開回到了TIOJ,準備拯救這一切。

「你真的很胖哎!」——CBD。


以上是題目敘述,相信你已經仔細的看完了。

Input Format

在你再看題目的同時,瑞南已經找到了傳說中的編譯器的位置了。
但是瑞南為了確保自己跟編譯器不會因為某些原因而發生種種可能要被「好,船」(Nice,Boat)的事情,他打算先觀察一下這個小島上的編譯器。
這個小島上的編譯器剛好都有一些數值,我們稱他為感情參數,分成兩種,「傲嬌編譯器」和「病嬌編譯器」,其中病嬌可能會在很奇怪的地方讓你Runtime Error。
瑞南發現,想要成功AC這題,如果把編譯器排成一排,每個編譯器都有一些感情參數,以一個數字表示。
你必須要找出一段安全區間,不論是從左邊一路走過去,或是從右邊一路走回來,編譯器的感情參數總和不可以是負數,不然這些編譯器可能會做出非常「好船」(Nice Boat)的事情。

「嗯,這code感覺完全沒有問題,好,傳囉(Nice,Boat)!」瑞南說。

你,擔心傳說中的編譯器被解除封印之後,世界上就會出現一堆持久化的<周強.h>,所以你也決定跟在瑞南的後面去看看,但是你必須分析一下瑞南的紀錄。

因為瑞南的long long最近去法國玩了,題目裡不會出現絕對值大於231 -1的數字。
紀錄中第一行有一個整數T,代表有幾組資料。
每一組資料第一行有一個整數N,
接下來有N個整數Ai,每個數字代表編號i的編譯器的感情參數,如果是正數代表她很傲嬌,如果是負數代表她很病嬌,如果一段區間的感情參數總和偏向病嬌的話你就會Runtime Error,你不希望這樣。

簡單來說,如果你可以找出一個區間,他的前綴和每個數字都大於等於0,而且他的後綴和的每個數字也都大於等於0,我們就稱他是安全區間,請你找出最長的安全區間長度是多少。

對於30%的測試資料,1≤N≤10000。
對於所有的測資,N≤1000000。

Output Format

輸出一個數字代表最長的安全區間(你不會Runtime Error的區間)。

Sample Input

2
10
-6 -4 -1 0 5 1 9 -8 -3 4
10
3 4 8 -7 6 -3 1 -7 2 9

Sample Output

4
10

Hints

對於第一筆測資,0 5 1 9 這4個數字前綴和後綴和每個數字都是大於等於0的,所以答案是4。
第2筆測資,整個區間的前綴和和後綴和每個數字都大於等於0,所以答案是10。

Problem Source

改編自POI 21-1(推廣)
果茶在1!時室友的胡言亂語。

Subtasks

For Testdata: 0 ~ 2, Score: 30
For Testdata: 3 ~ 9, Score: 70
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536