問題一覧 > 通常問題

No.2423 Merge Stones

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 34
作問者 : dyktr_06dyktr_06 / テスター : 👑 Nafmo2Nafmo2 firiexpfiriexp LaFolia13LaFolia13 sepa38sepa38 Seed57_cashSeed57_cash UdonUdon
3 ProblemId : 9804 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-12 13:32:25

問題文

$N$ 個の魔法石が円周上に並んでおり、反時計回りに $1, 2, …, N$ の番号がついています。番号 $i$ の魔法石の魔力は $A_i$ です。

また、魔法石にはそれぞれ色がついています。魔法石の色は整数で表され、番号 $i$ の魔法石の色は $C_i$ です。

あなたは、以下の操作を何度でも行うことができます。

  • 隣り合っている $2$ つの魔法石であって、色の整数の差が $K$ 以下であるようなものを選び合成する。 合成前の魔法石の魔力を $x$ および $y$ とすると、合成後の魔法石の魔力は $x + y$ となる。 合成後の魔法石の色については、合成前の魔法石の色のどちらかを選ぶことができる。

なお、合成前と後で魔法石の位置関係は変動しません。

全ての操作を行った後に、あなたは並んでいる魔法石の中から $1$ つを選ぶことができます。

選ぶことのできる魔法石の魔力としてありうる最大値を求めてください。

制約

  • $1 \leq N \leq 300$
  • $0 \leq K \leq 5$
  • $1 \leq A_i \leq 10^{9}$
  • $1 \leq C_i \leq 50$
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$  
$A_1$ $A_2$ ... $A_N$ 
$C_1$ $C_2$ ... $C_N$

出力

問題の答えを一行に出力せよ。

サンプル

サンプル1
入力
6 1
10 10 5 10 38 5
3 4 1 3 6 2
出力
40

以下のような手順で魔力が $40$ であるような魔法石を選ぶことができます。

また、$2$ 回目以降の魔法石の並びは直前の操作で合成した魔法石を基準に反時計回りで考えることにします。

  • 反時計回りで $1$ 番目と $2$ 番目の魔法石を合成し、色を $3$ とする。
    • 合成後の魔法石から反時計回りに魔力は $(20, 5, 10, 38, 5)$、色は $(3, 1, 3, 6, 2)$ となる。
  • 反時計回りで $1$ 番目と $5$ 番目の魔法石を合成し、色を $2$ とする。
    • 合成後の魔法石から反時計回りに魔力は $(25, 5, 10, 38)$、色は $(2, 1, 3, 6)$ となる。
  • 反時計回りで $1$ 番目と $2$ 番目の魔法石を合成し、色を $2$ とする。
    • 合成後の魔法石から反時計回りに魔力は $(30, 10, 38)$、色は $(2, 3, 6)$ となる。
  • 反時計回りで $1$ 番目と $2$ 番目の魔法石を合成し、色を $3$ とする。
    • 合成後の魔法石から反時計回りに魔力は $(40, 38)$、色は $(3, 6)$ となる。
  • 操作を終了し、魔力が $40$ である魔法石を選ぶ。
どのように操作を行っても魔力が $40$ より大きい魔法石を選ぶことはできないため、$40$ と出力します。

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