問題一覧 > 通常問題

No.2617 Knapsack with Capacity 3

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 37
作問者 : startcpp / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 7736 / 自分の提出
問題文最終更新日: 2023-12-23 20:02:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 416 (順位表) の他の問題:

Problem Statement

There are $N$ items and $K$ knapsacks.
The items are numbered from $1$ to $N$, and the knapsacks are numbered from $1$ to $K$.
Item $i$ has weight $w_i$ and value $v_i$.

Start-kun puts some items into each knapsack.
Some knapsacks may be left empty, but
for every knapsack, the total weight of the items put into it must be at most $3$.

What is the maximum possible total value of the items put into the $K$ knapsacks?

$w_i$ and $v_i$ are determined by a recurrence using the parameters $seed, a, b, m$.
Specifically, with % denoting the remainder operation, the recurrence
$f_1 = seed$
$f_{i + 1} = (a \times f_i + b)$ % $m$; $1 \le i \lt 2N$
generates the sequence $(f_1, \cdots, f_{2N})$, and then, for $i = 1, \cdots, N$,
$w_i = f_i$ % $3 + 1$
$v_i = w_i \times f_{N + i}$
are defined as above.

Input

$N$ $K$ $seed$ $a$ $b$ $m$

All input values are integers.
$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$

Output

Output an integer representing the maximum total value on $1$ line.
Print a newline at the end.

Sample

Sample 1
Input
6 2 15 26 31 97
Output
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)$
hold. It is optimal to put item $4$ into knapsack $1$ and items $3, 6$ into knapsack $2$. The answer is $184 + 285 + 67 = 536$.

Sample 2
Input
100 25 5049654 306283215 360320319 370412443
Output
21985715485

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。