AT_abc251_b.[ABC251B] At Most 3 (Judge ver.)

入门

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $N$ 个砝码，分别为砝码 $1$ 、砝码 $2$ 、 $\dots$ 、砝码 $N$ 。砝码 $i$ 的重量为 $A_i$ 。
满足以下条件的正整数 $n$ 被称为好整数：

可以任意选择不超过 $3$ 个不同的砝码，使得所选砝码的重量之和等于 $n$ 。

在不超过 $W$ 的正整数中，有多少个好整数？

输入格式

输入以如下格式从标准输入读入。

$N$ $W$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出答案。

输入输出样例

输入#1
```
2 10
1 3
```
输出#1
```
3
```
输入#2
```
2 1
2 3
```
输出#2
```
0
```
输入#3
```
4 12
3 3 3 3
```
输出#3
```
3
```
输入#4
```
7 251
202 20 5 1 4 2 100
```
输出#4
```
48
```

说明/提示

限制条件

$1\leq N\leq 300$
$1\leq W\leq 10^6$
$1\leq A_i\leq 10^6$
输入的所有数值均为整数

样例解释 1

只选择砝码 $1$ ，重量之和为 $1$ ，因此 $1$ 是好整数。只选择砝码 $2$ ，重量之和为 $3$ ，因此 $3$ 是好整数。选择砝码 $1$ 和砝码 $2$ ，重量之和为 $4$ ，因此 $4$ 是好整数。除此之外不存在其他好整数，并且 $1,3,4$ 都不超过 $W$ ，所以答案为 $3$ 个。

样例解释 2

不存在不超过 $W$ 的好整数。

样例解释 3

好整数为 $3,6,9$ ，共 $3$ 个。例如选择砝码 $1$ 、砝码 $2$ 、砝码 $3$ ，重量之和为 $9$ ，因此 $9$ 是好整数。注意 $12$ 不是好整数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页