a597. B. DD的背包問題 - 旦旦解題農場

內容

Jet身為一個DD，不只訂閱了很多Vtuber，還常常加入會員和丟Super Chat

但是Jet一個月能靠打麻將賺到的錢是有限的

所以他必須做出對於DD來說殘酷的抉擇

注意，因為金錢有限，不是每個頻道都必須訂閱 (DD之恥)

輸入說明

每個測資點單筆測資

第一行有兩正整數 $n,c$ ( $n\leq 10^3$ , $c\leq 10^5$ )

代表總共有 $n$ 個Jet想加入會員的頻道

那個月打麻將賺到的錢有 $c$

接下來有 $n$ 行，每行共有 $2k+1$ 個正整數

首先會有一數 $k$ 代表這頻道共有幾種訂閱層級 ( $k\leq 5$ )

接下來會有 $2k$ 個，兩個一組 $a_i,b_i$ ( $a_i,b_i \leq 10^5$ )

分別代表該訂閱層級讓Jet開心的程度及花費

輸出說明

輸出Jet能獲得的最大開心程度

範例輸入

5 2000
1 100 75
3 100 75 200 300 300 750
1 100 75
1 100 75
3 100 75 200 150 300 300

範例輸出

測資資訊：

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

提示：

範例測資依序為:

Nabi Suisei Rushia Uto HAACHAMA

標籤:

DP knapsack

出處:

DDJ Regular Contest Round#4 [管理者：

fdhs107_KonChin... (konchin)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」