No.1515 Making Many Multiples
だれ
nok0問題文
$N+2$ 枚のカードと正の整数 $K$ を用いてゲームを行います。各カードにはそれぞれ $1$ つの正の整数が書かれています。
$N$ 枚のカードは $1$ つの山になって置かれています。残りの $2$ 枚はあなたが初めから持っていて、 $1$ 枚には $X$、もう $1$ 枚には $Y$ が書かれています。
あなたは以下の操作を $N$ 回行います。
$(1)$ 山札の一番上のカードを引く。
$(2)$ 今手に持っているカードに書かれた数の和が $K$ の倍数であるとき、$1$ 点を得る。
$(3)$ 手に持っているカードのどれか $1$ 枚を捨てる。
あなたは超能力者なので、山札の上から $i$ 番目のカードには $A_i$ が書いてあることがわかりました。
最適に行動したとき、得られる得点の最大値を求めてください。
入力
$N\ K\ X\ Y$ $A_1\ A_2\ \dots \ A_N$
- $1 \leq N \leq 2000$
- $1 \leq K \leq 2000$
- $1 \leq X, Y, A_i \leq 10^9$
- 入力はすべて整数
出力
得られる得点の最大値を出力してください。 最後に改行してください。
サンプル
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。