P84450

Wilcze doły

难度 未定 单调队列 贪心
讨论 统计 4通过 13提交 30.8%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

字节城国王 Bajtazar III 雄心勃勃,计划攻打敌方城堡。城堡三面环绕难以逾越的护城河,Bajtazar 只能从第四面城墙发起进攻。然而,敌人在城墙外挖了 n 个深不可测的狼坑来阻碍进攻。Bajtazar 希望攻击尽可能长的连续城墙段,为此需填平部分狼坑。他决定用沙袋填埋一些坑,用巨型木板覆盖另一些坑。

城墙外有 n 个狼坑,Bajtazar 拥有 p 袋沙子,填埋第 i 个坑需 w_i 袋沙子。巨型木板可覆盖 d 个连续的坑。请你帮助 Bajtazar 计算通过最佳利用沙袋和木板,他能填平的最长连续狼坑段的长度。

输入

第一行包含三个整数 n, p, d (1 \leq d \leq n \leq 2000000, 0 \leq p \leq 10^{16}),分别表示狼坑数量、沙袋数量和巨型木板可覆盖的连续坑数。

第二行包含 n 个整数 w_1, w_2, \ldots, w_n (1 \leq w_i \leq 10^9),w_i 表示填埋第 i 个狼坑所需的沙袋数。

输出

输出一行,一个整数,表示 Bajtazar 可攻击的最长连续城墙段的狼坑数。

样例

样例 1
输入
9 7 2
3 4 1 9 4 1 7 1 3
输出
5

来源

POI2025

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交