No.2617 容量3のナップザック
タグ : / 解いたユーザー数 37
作問者 :
startcpp
/ テスター :
👑 
p-adic
問題文
$N$ 個のアイテムと、$K$ 個のナップザックがあります。
アイテムには $1$ から $N$ までの番号が振られており、ナップザックには $1$ から $K$ までの番号が振られています。
アイテム $i$ の重さは $w_i$ で、価値は $v_i$ です。
すたーと君は、それぞれのナップザックにいくつかのアイテムを入れます。
何も入れないナップザックがあっても構いませんが、
どのナップザックについても、入れるアイテムの重さの合計が $3$ 以下になるようにします。
このとき、$K$ 個のナップザックに入れるアイテムの価値の総和を、最大でいくらにできるでしょうか？
$w_i$ と $v_i$ はパラメータ $seed, a, b, m$ を使った漸化式によって定められます。
具体的には、% を余り演算としたとき
$f_1 = seed$
$f_{i + 1} = (a \times f_i + b)$ % $m$; $1 \le i \lt 2N$
という漸化式で数列 $(f_1, \cdots, f_{2N})$ を生成したのち、$i = 1, \cdots, N$ について
$w_i = f_i$ % $3 + 1$
$v_i = w_i \times f_{N + i}$
と定めます。
入力
$N$ $K$ $seed$ $a$ $b$ $m$
入力は整数
$1 \le K \le N \le 10^6$
$3 \le m \le 10^9$
$1 \le a \lt m$
$1 \le b \lt m$
$1 \le seed \lt m$
出力
価値の総和の最大値を表す整数を $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
6 2 15 26 31 97
出力
536
$(w_1, w_2, w_3, w_4, w_5, w_6) = (1, 1, 2, 3, 2, 1)$
$(v_1, v_2, v_3, v_4, v_5, v_6) = (22, 21, 184, 285, 152, 67)$
になります。アイテム $4$ をナップザック $1$ に、アイテム $3, 6$ をナップザック $2$ に入れたときが最適です。答えは $184 + 285 + 67 = 536$ になります。
サンプル2
入力
100 25 5049654 306283215 360320319 370412443
出力
21985715485
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。