102511: [AtCoder]ABC251 B - At Most 3 (Judge ver.)
Description
Score : $200$ points
Problem Statement
There are $N$ weights called Weight $1$, Weight $2$, $\dots$, Weight $N$. Weight $i$ has a mass of $A_i$.
Let us say a positive integer $n$ is a good integer if the following condition is satisfied:
- We can choose at most $3$ different weights so that they have a total mass of $n$.
How many positive integers less than or equal to $W$ are good integers?
Constraints
- $1 \leq N \leq 300$
- $1 \leq W \leq 10^6$
- $1 \leq A_i \leq 10^6$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $W$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Print the answer.
Sample Input 1
2 10 1 3
Sample Output 1
3
If we choose only Weight $1$, it has a total mass of $1$, so $1$ is a good integer.
If we choose only Weight $2$, it has a total mass of $3$, so $3$ is a good integer.
If we choose Weights $1$ and $2$, they have a total mass of $4$, so $4$ is a good integer.
No other integer is a good integer. Also, all of $1$, $3$, and $4$ are integers less than or equal to $W$. Therefore, the answer is $3$.
Sample Input 2
2 1 2 3
Sample Output 2
0
There are no good integers less than or equal to $W$.
Sample Input 3
4 12 3 3 3 3
Sample Output 3
3
There are $3$ good integers: $3, 6$, and $9$.
For example, if we choose Weights $1$, $2$, and $3$, they have a total mass of $9$, so $9$ is a good integer.
Note that $12$ is not a good integer.
Sample Input 4
7 251 202 20 5 1 4 2 100
Sample Output 4
48
Input
题意翻译
有 $n$ 个数,最多选 $3$ 个,总和正好凑到 $w$ 及以下的有几个。 Translated by @[$\tt{\_YXJS\_}$](/user/516346).Output
问题描述
有$N$个重量,分别叫做 Weight $1$, Weight $2$, $\dots$, Weight $N$。Weight $i$的重量是$A_i$。
让我们定义一个正整数$n$是好整数,如果满足以下条件:
- 我们可以选择最多3个不同的重量,使它们的总重量为$n$。
有多少个小于等于$W$的正整数是好整数?
限制条件
- $1 \leq N \leq 300$
- $1 \leq W \leq 10^6$
- $1 \leq A_i \leq 10^6$
- 输入中的所有值都是整数。
输入
输入从标准输入按以下格式给出:
$N$ $W$ $A_1$ $A_2$ $\dots$ $A_N$
输出
打印答案。
样例输入1
2 10 1 3
样例输出1
3
如果我们只选择Weight $1$,它的总重量是$1$,所以$1$是好整数。
如果我们只选择Weight $2$,它的总重量是$3$,所以$3$是好整数。
如果我们选择Weight $1$和$2$,它们的总重量是$4$,所以$4$是好整数。
没有其他整数是好整数。另外,所有小于等于$W$的$1$、$3$和$4$都是好整数。因此,答案是$3$。
样例输入2
2 1 2 3
样例输出2
0
没有小于等于$W$的好整数。
样例输入3
4 12 3 3 3 3
样例输出3
3
有$3$个好整数:$3, 6$, 和 $9$。
例如,如果我们选择Weight $1$、$2$和$3$,它们的总重量是$9$,所以$9$是好整数。
注意$12$不是好整数。
样例输入4
7 251 202 20 5 1 4 2 100
样例输出4
48