Trous de Loup
Time limit2sMemory limit512 MB
Given n weighted positions, a sandbag budget p, and a plank covering d consecutive positions, find the longest contiguous segment that can be fully disarmed.
- Level
Medium7 of 10
- Topics
- Sliding window, Two pointers, Binary search, Prefix sum
- Solved
- No attempts yet
Problem
Byteasar III the Bold, King of Byteotia, is planning a raid on an enemy castle. The castle is surrounded on three sides by an impassable moat, so Byteasar has no choice but to lay siege to the fourth side. That side is not completely unprotected either: the royal scouts have reported deep trous de loup along this wall. Byteasar wants to attack the longest possible contiguous segment of the wall. To do this, some of the trous de loup must be disarmed. The wise king has decided to fill some of them with sand and to cover some with the Great Plank.
There are n trous de loup along the wall. The king's troops have p sandbags. Filling the i-th trou de loup requires wi sandbags. The Great Plank can cover up to d successive trous de loup.
Help Byteasar find the longest segment of the wall his troops can attack when they use their resources (the sandbags and the Great Plank) optimally. In other words, determine the maximum number of successive trous de loup that can be disarmed.
Input
The first line contains three integers n, p, and d, separated by single spaces: the number of trous de loup, the number of sandbags, and the length of the Great Plank. (1 ≤ d ≤ n ≤ 2 000 000, 0 ≤ p ≤ 10^16)
The next line contains a sequence of n integers w1, w2, ..., wn separated by single spaces. (1 ≤ wi ≤ 10^9) wi is the number of sandbags required to fill the i-th trou de loup. In tests worth 30% of the total score, the additional condition n ≤ 3000 holds.
Output
The first and only line should contain a single integer: the length of the longest contiguous segment of the wall that the king's troops can attack.
Hint
Trous de loup 2, 3, and 6 can be filled with sand (using 6 of the 7 available bags), while 4 and 5 can be covered with the Great Plank. This way, five successive trous de loup (numbers 2 to 6) are disarmed.