No.1515 Making Many Multiples
Problem Statement
You play a game using $N+2$ cards and a positive integer $K$. Each card has $1$ positive integer written on it.
$N$ of the cards are placed in $1$ pile. You hold the remaining $2$ cards from the beginning: $1$ of them has $X$ written on it, and the other $1$ has $Y$ written on it.
You perform the following operation $N$ times.
$(1)$ Draw the top card of the pile.
$(2)$ If the sum of the numbers written on the cards currently in your hand is a multiple of $K$, gain $1$ point.
$(3)$ Discard any $1$ of the cards in your hand.
Since you are a psychic, you know that the $i$-th card from the top of the pile has $A_i$ written on it.
Find the maximum score you can obtain when you act optimally.
Input
$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$
- All inputs are integers.
Output
Output the maximum score you can obtain. Print a newline at the end.
Sample
Sample 1
Input
3 3 1 2 3 4 5
Output
3
In operation $1$, discard the card with $1$, and in operation $2$, discard the card with $2$; this way, you can obtain $3$ points.
Initially, you hold the card with $1$ and the card with $2$.
In operation $1$, you draw the card with $3$. Here, $1+2+3=6$ is a multiple of $3$, so you gain $1$ point.
You discard the card with $1$. You now hold the cards with $2$ and $3$.
In operation $2$, you draw the card with $4$ written on it. $2+3+4=9$ is a multiple of $3$, so you gain $1$ point.
You discard the card with $2$. You now hold the cards with $3$ and $4$.
In operation $3$, you draw the card with $5$ written on it. $3+4+5=12$ is a multiple of $3$, so you gain $1$ point.
You may discard any card.
By acting as above, you obtain $3$ points, and this is the maximum.
Sample 2
Input
5 100 1 1 1 1 1 1 1
Output
0
No matter how you act, you cannot obtain even $1$ point.
Sample 3
Input
10 3 2 2 3 3 3 3 3 2 2 2 2 2
Output
6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
だれ
nok0