d035. P_3_7 . 正整數序列之最接近的區間和

Content

輸入一個正整數序列 $(A_1, A_2, …, A_n)$，另外給了一個非負整數 $K$，請計算哪些連續區段的和最接近 $K$ 而不超過 $K$，以及這樣的區間有幾個。$n$ 不超過 $20$ 萬，輸入數字與 $K$ 皆不超過 $10$ 億。

Input

第一行是 $n$ 與 $K$，第二行 $n$ 個整數是 $A_i$，同行數字以空白間隔。

Output

第一行輸出最接近 $K$ 但不超過 $K$ 的和，第二行輸出這樣的區間有幾個。

Sample Input #1

5 10
4 3 1 7 4

Sample Output #1

8
2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (20%): 1.0s , <10M
公開測資點#1 (20%): 1.0s , <10M
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (20%): 1.0s , <10M
公開測資點#4 (20%): 1.0s , <10M

Hint ：

Tags:

ch3

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」