d020: 例題 P-2-11. 最接近的區間和 (*)
Tags :
Accepted rate : 162人/242人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-03-04 17:46

Content

輸入一個整數序列 $(A[1], A[2], ..., A[n])$ ,另外給了一個非負整數 $K$ ,

請計算哪一個連續區段(含空區間,和為 $0$)的和最接近 $K$ 而不超過 $K$。

Input

第一行是 $n$ 與 $K$,

第二行 $n$ 個整數是 $A[i]$,

同行數字以空白間隔。

$n$ 不超過 10 萬,數字總和不超過 10 億。

Output

在所有區間和中,最接近 $K$ 但不超過 $K$ 的和。

Sample Input #1
5 10
5 -5 8 -3 4
Sample Output #1
9
Sample Input #2
1 1
-1
Sample Output #2
0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (6%): 0.5s , <1M
公開 測資點#1 (6%): 0.5s , <1M
公開 測資點#2 (6%): 0.5s , <1M
公開 測資點#3 (6%): 0.5s , <1M
公開 測資點#4 (6%): 0.5s , <1M
公開 測資點#5 (6%): 0.5s , <1K
公開 測資點#6 (6%): 0.5s , <1M
公開 測資點#7 (6%): 0.5s , <1M
公開 測資點#8 (6%): 0.5s , <1M
公開 測資點#9 (6%): 0.5s , <1M
公開 測資點#10 (6%): 0.5s , <1M
公開 測資點#11 (6%): 0.5s , <1M
公開 測資點#12 (7%): 0.5s , <1M
公開 測資點#13 (7%): 0.5s , <1M
公開 測資點#14 (7%): 0.5s , <1M
公開 測資點#15 (7%): 0.5s , <1M
Hint :
Tags:
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


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