18368번 - Trous de loup 다국어

The King of Byteotia, Byteasar III the Bold, is planning a raid on enemy’s castle. On three sides, the castle is surrounded by impenetrable moat, leaving Byteasar no other option than to lay siege to the fourth side of the castle. However, it turns out that this side is not completely unprotected either: the royal scouts have reported that there are deep trous de loup along this wall. Byteasar would like to attack a contiguous segment of the wall as long as possible. To this end, some of the trous de loup will have to be disarmed. The wise king has decided to fill up some of them with sand, and to cover some with the Great Plank.

Along the wall, there are n trous de loup. King Byteasar’s troops have p sandbags. To fill up the i-th trou de loup, w_i of the sandbags are required. Moreover, the Great Plank can cover up to d successive trous de loup.

Help Byteasar in identifying the longest segment of the wall that his troops may attack if they utilize their resources (i.e., the sandbags and the Great Plank) optimally. In other words, determine what is the maximum number of successive trous de loup that can be disarmed.

The first line of the standard input contains three integers, n, p, and d (1 ≤ d ≤ n ≤ 2 000 000, 0 ≤ p ≤ 10¹⁶), separated by single spaces, which specify the numbers of trous de loup and of sandbags, and the length of the Great Plank respectively.

The next lines describes the trous de loup: it contains a sequence of n integers, w₁, w₂, . . . , w_n (1 ≤ w_i ≤ 10⁹) separated by single spaces; w_i is the number of sandbags required to fill up the i-th trou de loup. In tests worth 30% of the total score, an additional condition n ≤ 3000 holds.

The first and only line of the standard output should contain a single integer: the length of the longest contiguous segment of the wall that Byteasar’s troops can attack.

The trous de loup no. 2, 3, and 6 can be filled up with sand (using 6 out of the 7 bags available), whereas the ones no. 4 and 5 can be covered with the Great Plank. This way, five successive trous de loup (the ones no. 2 to 6) will be disarmed.