AT_ttpc2015_b.ラー油

普及-

通过率：0%

AC君温馨提醒

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

题目描述

东工太郎君在 $N$ 天里，每天都会吃一碗担担面。担担面可以根据喜好添加任意量的辣油。太郎君在第 $i$ 天（ $1 \leq i \leq N$ ）吃了加了 $x_i$ 辣油的担担面时，可以获得 $A_i x_i$ 的幸福度。

由于太郎君肠胃较弱，需要满足 $0 \leq x_i \leq B\ (1 \leq i \leq N)$ 且 $\sum_{1 \leq i \leq N} x_i \leq C$ 。另外，辣油非常美味，所以当 $N \geq 2$ 时，对于任意的 $i(1 \leq i \leq N-1)$ ，都有 $A_i \leq A_{i+1}$ 。

请你求出太郎君在 $N$ 天内能够获得的幸福度总和的最大值。

输入格式

输入通过标准输入给出，格式如下：

$N$ $B$ $C$ $A_1$ $...$ $A_N$

第 $1$ 行包含三个整数 $N(1 \leq N \leq 100)$ 、 $B(1 \leq B \leq 10000)$ 、 $C(1 \leq C \leq 10000)$ ，以空格分隔。
第 $2$ 行包含 $N$ 个整数 $A_1, \ldots, A_N\ (0 \leq A_i \leq 100)$ ，以空格分隔。
当 $N \geq 2$ 时，对于任意的 $i(1 \leq i \leq N-1)$ ，都有 $A_i \leq A_{i+1}$ 。

输出格式

请输出太郎君在 $N$ 天内能够获得的幸福度总和的最大值，输出占一行，末尾需换行。

输入输出样例

输入#1
```
3 2 5
1 2 3
```
输出#1
```
11
```
输入#2
```
3 100 100
1 2 100
```
输出#2
```
10000
```
输入#3
```
5 0 10000
1 2 3 7 15
```
输出#3
```
0
```
输入#4
```
6 10000 0
1 2 4 8 16 97
```
输出#4
```
0
```
输入#5
```
5 10000 10000
0 0 0 0 0
```
输出#5
```
0
```
输入#6
```
8 5 32
0 1 1 2 3 5 8 13
```
输出#6
```
162
```

说明/提示

样例解释 1

第 $1$ 天加 $1$ 份辣油，第 $2$ 天和第 $3$ 天各加 $2$ 份辣油是最优的，太郎君能获得 $11$ 的幸福度。

样例解释 2

第 $1$ 天和第 $2$ 天都不加辣油，第 $3$ 天加 $100$ 份辣油是最优的，太郎君能获得 $10000$ 的幸福度。

样例解释 3

太郎君无法再额外加辣油。

样例解释 4

太郎君的肠胃太弱，无法再加辣油。

样例解释 5

无论加多少辣油，太郎君都无法获得幸福。

由 ChatGPT 4.1 翻译

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

首页