Problem : 185 - 噪音取締

Problem Statistics

Solved Member: 36　　Submission: 143　　User Tried: 39

Statement:

Farmer John有很多乳牛

FJ的生意越作越大，乳牛越養越多，產生的噪音終於有一天讓鄰居忍無可忍了！
FJ被檢舉了，他收到美國中央乳牛情報管理局(中乳局)的通知，表示要派人來對FJ的農場進行抽檢

農場裡的牛槽是呈一字排開，一個牛槽一頭牛
例如有N頭牛的話，那麼我們這裡說牠們編號1~N
抽檢的方法是，隨機取一段區間[a,b](其中1≦a≦b≦N)，計算並檢驗每一頭牛發出的噪音總和是否超過K
(事實上FJ並不清楚中乳局詳細的抽檢方法，他想成所有區間被使用的機率都是相等的)
明天一大早中乳局的官員就要來了，FJ想知道有多少種區間組合會讓他超標並且吃罰單

Input:Output:

每個測試檔僅有一筆測試資料。
第一行有兩個正整數N,K，表示有N頭乳牛一字排開，以及噪音標準值K(N≦100000,K≦1000000000)
第二行有N個正整數，依序表示這編號1~N各乳牛發出的噪音量(每個噪音量不會超過20000)

請輸出唯一的一行，包含一個非負整數，表示噪音總和大於K的區間總數

Sample Input:Sample Output:

4 4
1 2 5 2

HINT:

範例測資中的六種區間分別是
[1,3]=8
[1,4]=10
[2,3]=7
[2,4]=9
[3,3]=5
[3,4]=7

Source:

101校內培訓

Problem Setter

lajisongyy_jack1

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10