現在還是雲端大數據物聯網的時代,社群網站上無時無刻仍然有著海量的廢文被發表。
這次,你手上的資料換成了全球網路廢文資料集(data set),試圖從中得到珍貴的資訊。
你在茫茫廢文海中發現了一個使用者 — Eddy — 所發的廢文特別有深意,在數位的時代,他所發的所有廢文被編碼成了一串整數 $a_1,a_2,\ldots,a_n$。第 $i$ 個整數代表 Eddy 在第 $i$ 天所發的廢文。數字的大小有它的意義,當我們看了一篇被編碼成數字 $x$ 的廢文之後,我們心靈的正面能量值會加上 $x$。當正面能量值掉到小於 $0$ 時,我們會變得內心扭曲,言行不得體,毀家廢婚,面容猥瑣,這是很不好的事情。
為了大家好,你想要檢查 Eddy 所發的廢文會不會造成社會道德危機。我們在看一個人發的廢文時,常常都是從某一則廢文開始,照著發表時間一篇一篇看,看到不想看為止。我們可以定義「看法」為一組 $(l, r)$,代表依序把 $a_l,a_{l+1},\ldots,a_r$ 這幾篇廢文看過。而「不道德」的看法則是在觀看廢文的過程中,會有某些時刻使得起始正面能量值為$0$的人內心扭曲。例如 Eddy 發了 $100, -300, 200, 400$ 這幾篇廢文,那 $(3, 4)$ 是一組道德的看法 (觀看 $200, 400$ 的過程中正面能量值總是不小於 $0$),$(1, 4)$ 則是不道德的看法,因為看完第 2 篇時正面能量值為 $-200$,這是內心扭曲的證據。
你想要知道,Eddy 所發的廢文,有幾種不道德的看法。
測試資料共包含兩行。
第一行有一個正整數 $n$,表示 Eddy 所發的廢文數量。第二行有 $n$ 個以空格隔開的整數,第 $i$ 個數字 $a_i$ 表示 Eddy 於第 $i$ 天所發的廢文。
輸出一行包含一個非負整數,代表 Eddy 廢文裡不道德看法的數量。
2016 NPSC高中組決賽
No. | Testdata Range | Score |
---|---|---|
1 | 0~35 | 100 |