問題一覧 > 通常問題

No.3097 Azuki Kurai

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 16
作問者 : RiRinbaru / テスター : 👑 ygussany autumn09 Yotugi hamo21
3 ProblemId : 12103 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-04-06 13:27:52

問題文

NN 人の村人が円形に並んだ家に住んでいます。ある家を家 11 と定義し、そこから時計回りにそれぞれの家を家 2,3,...,N2, 3, ..., N と定義します。
それぞれの村人は小豆を持っており、家 ii に住む村人の持つ小豆の量は数列 A=(A1,A2,...,AN)A=(A_1, A_2, ..., A_N) を用いて AiA_i と与えられます。

妖怪であるRiRinbaru君は毎晩村人たちの家に忍びこみ、その家にある小豆をすべて食べつくしてしまいます。 村人たちは妖怪に小豆を取られたくないので、毎日隣の家に小豆を KK だけ移動することができます。 すなわち、すべての村人は自分の持っている小豆のうち、非負整数である数として KK 以下の量を選び、それを非負整数である量 22 つに分けた後にそれぞれをその両隣の人の家に移動させます。分ける量は 00 としても問題ありません。

厳密な定義 以下のこの順番で起きる2つの操作をひとまとまりとして 11 日に起こることとします。
  • 家 i(1≤i≤N)i(1\leq i\leq N) について、以下の操作をすべての家に対して同時に行う。 非負整数である 00 以上 KK 以下の数を選び、その家に住む村人の小豆からその非負整数だけの量を減らす。家にある小豆の量が 00 未満になるようには減らせない。 その後、減らした小豆を 00 以上の非負整数の量2つに分ける。そして、それらの小豆をそれぞれ家 i−1,i+1i-1, i+1 のもつ小豆に加える。 ただし、家 00 は家 NN を、家 N+1N+1 は家 11 を表すとする。
  • RiRinbaru君がある家に忍び込む。忍び込まれた家にある小豆の量は 00 となる。

占い師のおかげで、今後 MM 日間、それぞれの日にRiRinbaru君が忍び込む家が判明しています。具体的には、ii 日目に忍び込む家は数列 B=(B1,B2,...,BM)B=(B_1, B_2,..., B_M) を用いて BiB_i と表されます。
このとき、以下の問題について i=1,2,...,Mi=1, 2, ..., M としたときのそれぞれの答えを出力してください。

ii 日後における村全体で食べられていない小豆の量の総和の最大値を求めてください。

入力

N M KN\ M\ K
A1 A2 ... ANA_1\ A_2\ ...\ A_N
B1 B2 ... BMB_1\ B_2\ ...\ B_M

  • 3≤N≤93\leq N\leq 9
  • 1≤M≤2×1031\leq M\leq 2×10^3
  • 1≤K≤1091\leq K\leq 10^9
  • 0≤Ai≤109(1≤i≤N)0\leq A_i\leq 10^9(1\leq i\leq N)
  • 1≤Bi≤N(1≤i≤M)1\leq B_i\leq N(1\leq i\leq M)
  • 入力はすべて整数

出力

i (1≤i≤M)i\ (1\leq i\leq M) 日後における村全体で食べられていない小豆の量の総和の最大値をそれぞれ出力してください。
1行ごとに、そして最後に改行してください。

サンプル

サンプル1
入力
4 2 10
21 10 30 40
2 1
出力
101
100

1日目には家 22 に忍び込むので、小豆が食べられるのを避けるために家 22 の小豆をすべて家 33 に移します。また、家 11 の小豆のうち 1010 を家 44 に移します。
この場合、44 つの家全体で 101101 の小豆が残っていることになります。小豆の量が最初の総量から増えることはなくこれが最大値であるため、101 と出力してください。
2日目には家 11 に忍び込むので、小豆が食べられるのを避けるために家 11 の小豆のうち 1010 を家 44 に移します。結果家 22 に残っていた小豆 11 は食べられてしまいます。
この場合、44 つの家全体で 100100 の小豆が残っていることになります。すべての小豆を食べられないようにする移動方法は存在せず、この移動方法が食べられていない小豆の量の最大値を実現する方法のうちの1つであるため、100 と出力してください。

サンプル2
入力
3 3 100000000
70000000 100000000 130000000
2 1 3
出力
300000000
300000000
300000000

3日間すべてにおいてすべての小豆を食べられないように移動する方法が存在するので、Ai(1≤i≤N)A_i(1\leq i\leq N) の総和である 300000000 を 33 回出力してください。

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