ABC478 B - Topping

トッピング

考え方

$3$ 重ループで $1\leq i<j<k\leq N$ の範囲で全探索をすればよい。
価格が $V$ を超えていたらその候補はスキップし、そうでなければ最大嬉しさの記録を更新すればよい。

問題は、配列を普通に受け取ると 0-indexed になってしまうこと。
これにはいくつか解決策がある。

最も単純な方法としては、基準値を $V$ ではなく $V-3$ にすること。
0-indexed と 1-indexed の差である $3$ をこれで吸収できる。

あるいは、価格 $0$ で嬉しさが $-\infty$ のものを先頭にダミーとして用意してもよい。

入力を受け取る。

n: 5
v: 9
w: {31, 41, 59, 26, 53}

0-indexed では価格の条件を $i+j+k\leq V-3=6$ として、$0\leq i<j<k<5$ を全探索する。

条件を満たす候補は次の通り。

$i$	$j$	$k$	トッピング番号	価格の合計	嬉しさの合計
$0$	$1$	$2$	$1,2,3$	$6$	$31+41+59=131$
$0$	$1$	$3$	$1,2,4$	$7$	$31+41+26=98$
$0$	$1$	$4$	$1,2,5$	$8$	$31+41+53=125$
$0$	$2$	$3$	$1,3,4$	$8$	$31+59+26=116$
$0$	$2$	$4$	$1,3,5$	$9$	$31+59+53=143$
$1$	$2$	$3$	$2,3,4$	$9$	$41+59+26=126$

この中で嬉しさの合計が最大なのは、トッピング $1,3,5$ を選ぶときの $143$ である。

したがって、答えは $143$ となる。

特になし。

特になし。