AdditionalFile4973.zip

P3594 [POI 2015 R3] 狼坑 Trous de loup

题目描述

给定一个长度为 $n$ 的序列，你有一次机会选中一段连续的长度不超过 $d$ 的区间，将里面所有数字全部修改为 $0$。请找到最长的一段连续区间，使得该区间内所有数字之和不超过 $p$。

输入格式

输入的第一行包含三个整数，分别代表 $n,p,d$。

第二行包含 $n$ 个整数，第 $i$ 个整数代表序列中第 $i$ 个数 $w_i$。

输出格式

包含一行一个整数，即修改后能找到的最长的符合条件的区间的长度。

输入输出样例 #1

输入 #1

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

输出 #1

5

说明/提示

【数据范围】

对于 $100\%$ 的数据，$1 \le d \le n \le 2 \times 10^6$，$0 \le p \le 10^{16}$，$1 \leq w_i \leq 10^9$。

原题名称：Wilcze doły。

#4973. 「POI2015 R3」狼坑 Trous de loup

标签: 传统 | 时间限制: 4000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXII Olimpiada Informatyczna — III etap Wilcze doły

字节城国王 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 可攻击的最长连续城墙段的狼坑数。

样例

输入

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

输出

5

Bajtazar 可填埋第 $2$、$3$、$6$ 个坑（使用 $4+1+1=6$ 袋沙子，$7$ 袋中剩余 $1$ 袋），用巨型木板覆盖第 $4$、$5$ 个坑（$d=2$）。这样，他填平第 $2$ 到 $6$ 的 $5$ 个连续坑。

数据范围与提示

对于 $30\%$ 的数据，$n \leq 3000$。