問題一覧 > 通常問題

No.1515 Making Many Multiples

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : だれ / テスター : nok0
9 ProblemId : 6366 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-19 02:24:40

問題文

N+2 枚のカードと正の整数 K を用いてゲームを行います。各カードにはそれぞれ 1 つの正の整数が書かれています。

N 枚のカードは 1 つの山になって置かれています。残りの 2 枚はあなたが初めから持っていて、 1 枚には X、もう 1 枚には Y が書かれています。

あなたは以下の操作を N 回行います。

(1) 山札の一番上のカードを引く。
(2) 今手に持っているカードに書かれた数の和が K の倍数であるとき、1 点を得る。
(3) 手に持っているカードのどれか 1 枚を捨てる。

あなたは超能力者なので、山札の上から i 番目のカードには Ai が書いてあることがわかりました。

最適に行動したとき、得られる得点の最大値を求めてください。

入力

N K X Y
A1 A2 … AN

  • 1≤N≤2000
  • 1≤K≤2000
  • 1≤X,Y,Ai≤109
  • 入力はすべて整数

出力

得られる得点の最大値を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3 3 1 2
3 4 5
出力
3

1 回目の操作で 1 のカードを、 2 回目の操作で 2 のカードを捨てることで、3 点を得ることができます。


はじめ、あなたは 1 のカードと 2 のカードを持っています。

1 回目の操作で 3 のカードを引きます。このとき、 1+2+3=6 は 3 の倍数なので 1 点を得ます。

1 のカードを捨てます。あなたが持っているのは 2 と 3 のカードです。

2 回目の操作で 4 が書かれたカードを引きます。2+3+4=9 は 3 の倍数なので 1 点を得ます。

2 のカードを捨てます。あなたが持っているのは 3 と 4 のカードです。

3 回目の操作で 5 が書かれたカードを引きます。 3+4+5=12 は 3 の倍数なので 1 点を得ます。

捨てるカードはなんでもよいです。


以上のように行動することで 3 点を得られ、これが最大です。

サンプル2
入力
5 100 1 1
1 1 1 1 1
出力
0

どのように行動しても 1 点も得られません。

サンプル3
入力
10 3 2 2
3 3 3 3 3 2 2 2 2 2
出力
6

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