No.2429 Happiest Tabehodai Ways
タグ : / 解いたユーザー数 82
作問者 :
Koi
/ テスター :
0214sh7
noya2
👑 
potato167
tassei903
ramdos
ponjuice
問題文
Koi君は食べ放題のお店に来ました。このお店には $N$ 種類の料理があり、 $i$ 種類目の料理は カロリーが $C_i$ で美味しさが $D_i$ です。また、Koi君は満腹度と幸福度の $2$ つの値を持っています。はじめ、満腹度、幸福度はともに $0$ です。
Koi君は以下の一連の動作を好きなだけ行います。( $0$ 回でも良い)
- $1\leq i\leq N$ の整数 $i$ を $1$ つ選ぶ
- ( 満腹度 $+C_i )\leq K$ のとき $i$ 種類目の料理を食べ、満腹度を( 満腹度 $+C_i$ )に、幸福度を( 幸福度 $+D_i$ )に更新する。
一連の動作を好きなだけ行った後の幸福度の最大値を求めてください。 また、幸福度が最大になるような料理の食べ方が何通りあるかを $998244353$ で割った余りを求めてください。
ただし、料理の食べ方が異なるとは、以下の条件のいずれかを満たすことを言います。
- 食べた料理の個数が異なる。
- ある整数 $i$ が存在して、 $i$ 番目に食べた料理の種類が異なる。
制約
- 入力は全て整数
- $1\le N\le 1000$
- $1\le K\le 1000$
- $1\le C_i,D_i\le 1000 ( 1\le i\le N ) $
入力
$N K$ $C_1 C_2 ... C_N$ $D_1 D_2 ... D_N$
出力
$2$ 行出力してください。
$1$ 行目には幸福度の最大値を整数で出力してください。
$2$ 行目には幸福度が最大になるような料理の食べ方が何通りあるかを $998244353$ で割った余りを整数で出力してください。
サンプル
サンプル1
入力
3 5 2 3 5 1 10 11
出力
11 3
$1$ 種類目の料理、 $2$ 種類目の料理の順で食べることで幸福度が $11$ になります。幸福度が $11$ を超えることはないので幸福度の最大値は $11$ です。
他に幸福度が $11$ になる食べ方は $2$ 種類目の料理、 $1$ 種類目の料理の順に食べる方法と、 $3$ 種類目の料理だけ食べる方法の $2$ 通りあります。
サンプル2
入力
3 1 2 4 1000 800 900 1000
出力
0 1
何も食べられない場合もあることに注意してください。
サンプル3
入力
2 100 1 1 1 1
出力
100 882499718
$998244353$ で割った余りを出力してください。
サンプル4
入力
6 21 4 4 5 5 6 7 6 7 8 9 10 11
出力
37 9
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。