#P4385. [POI2015]Wilcze doły

    ID: 3588 传统题 1000ms 128MiB 尝试: 1086 已通过: 340 难度: 5 上传者: 标签>难度分类普及+/提高-排序与序列处理一维前缀和滑动窗口单调队列CF1800鸣谢Claris

[POI2015]Wilcze doły

[POI 2015] Wilcze doły 陷坑

题目描述

敌城能进攻的一面墙前有 nn 个依次排列的陷坑,将第 ii 个陷坑填平要用 wiw_i 袋沙。Bajtazar 有 pp 袋沙和一块长木板。木板可以一次盖住恰好 dd 个相邻的陷坑,盖住的坑不消耗沙袋。

用木板和沙袋使一段连续的陷坑都能通过。求这段连续的陷坑最多有多少个。

输入格式

第一行三个整数 n,p,dn,p,d(1≤d≤n≤2×1061\le d\le n\le2\times10^6、0≤p≤10160\le p\le10^{16})。

第二行 nn 个整数 w1,…,wnw_1,\dots,w_n(1≤wi≤1091\le w_i\le10^9)。

输出格式

输出一个整数,表示最多能通过的连续陷坑数。

样例 #1

样例输入 #1

9 7 2
3 4 1 9 4 1 7 1 3

样例输出 #1

5

提示

样例中用木板盖住第 4,54,5 个坑,再用 4+1+1=64+1+1=6 袋沙填平第 2,3,62,3,6 个坑,从而通过第 22 至第 66 个坑。

原赛共 30% 的分值满足 n≤3000n\le3000。原赛另描述了两组公开测试:第一组 n=100n=100、p=49p=49、d=50d=50、所有 wi=1w_i=1;第二组 n=500 000n=500\,000、p=1p=1、d=1000d=1000,奇数位置需一袋沙,偶数位置需两袋。