d019: 例題 Q-2-10. 子集合的和(折半枚舉)
Tags :
Accepted rate : 8人/9人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-01-27 10:41

Content

輸入 $n$ 個正整數 $A[1..n]$,另外給了一個整數 $P$,請計算 $A$ 中元素各種組合中,其和最接近 $P$ 但不超過 $P$ 的和是多少。每個元素可以選取或不選取但不可重複選,$A$ 中的數字可能重複。$A[i]$ 與 $P$ 均不超過 $2^{60}$,$0 < n \leq 38$。

Input

第一行是 $n$ 與 $P$,第二行 $n$ 個整數是 $A[i]$,同行數字以空白間隔。

Output

最接近 $P$ 但不超過 $P$ 的和。

Sample Input
5 17
5 5 8 3 10
Sample Output
16
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


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