AT_arc057_b.[ARC057B] 高橋君ゲーム

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

高桥君在 $N$ 天内玩游戏。第 $i$ 天（ $1 \leq i \leq N$ ），他玩了 $a_i$ 局游戏。

每局游戏的结果要么胜利，要么失败。

高桥君第 $i$ 天（ $1 \leq i \leq N$ ）的心情由胜率决定：如果截止到第 $i$ 天的累计胜率，严格高于截止到第 $i-1$ 天的累计胜率，则第 $i$ 天他心情好；否则，他心情不好。这里，截止到第 $i$ 天的累计胜率指的是：如果 $i=0$ ，则为 $0$ ，否则为截止到第 $i$ 天为止所有游戏的胜利次数之和除以游戏总次数之和。

高桥君的心情会直接影响 AtCoder 公司的收益，所以青木君很关心高桥君的心情。青木君知道高桥君在 $N$ 天内总共赢了 $K$ 局游戏。

请你帮青木君计算，高桥君心情好的天数的最大可能值。

输入格式

输入从标准输入读入，格式如下：

$N$ $K$ $a_1$ $a_2$ $\cdots$ $a_N$

输出格式

请输出高桥君心情好的天数的最大可能值，输出一行。

输入输出样例

输入#1
```
5 7
2
3
7
4
9
```
输出#1
```
3
```
输入#2
```
3 5
1
2
2
```
输出#2
```
1
```
输入#3
```
2 4
2
10
```
输出#3
```
1
```
输入#4
```
10 12
2
8
3
5
10
5
2
9
19
22
```
输出#4
```
7
```

说明/提示

限制条件

$1 \leq N \leq 2000$
$1 \leq a_i \leq 500000\ (1 \leq i \leq N)$
$0 \leq K \leq a_1 + a_2 + \cdots + a_N$

由 ChatGPT 4.1 翻译

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

首页