Curfew
Contest: Codeforces Round 469 (Div. 1)
Difficulty rating: 2300
Tags: binary search, brute force, greedy, sortings

Instructors of Some Informatics School make students go to bed.

The house contains n rooms, in each room exactly b students were supposed to sleep. However, at the time of curfew it happened that many students are not located in their assigned rooms. The rooms are arranged in a row and numbered from 1 to n. Initially, in i-th room there are ai students. All students are currently somewhere in the house, therefore a1 + a2 + ... + an = nb. Also 2 instructors live in this house.

The process of curfew enforcement is the following. One instructor starts near room 1 and moves toward room n, while the second instructor starts near room n and moves toward room 1. After processing current room, each instructor moves on to the next one. Both instructors enter rooms and move simultaneously, if n is odd, then only the first instructor processes the middle room. When all rooms are processed, the process ends.

When an instructor processes a room, she counts the number of students in the room, then turns off the light, and locks the room. Also, if the number of students inside the processed room is not equal to b, the instructor writes down the number of this room into her notebook (and turns off the light, and locks the room). Instructors are in a hurry (to prepare the study plan for the next day), so they don't care about who is in the room, but only about the number of students.

While instructors are inside the rooms, students can run between rooms that are not locked and not being processed. A student can run by at most d rooms, that is she can move to a room with number that differs my at most d. Also, after (or instead of) running each student can hide under a bed in a room she is in. In this case the instructor will not count her during the processing. In each room any number of students can hide simultaneously.

Formally, here is what's happening:

- A curfew is announced, at this point in room i there are ai students.
- Each student can run to another room but not further than d rooms away from her initial room, or stay in place. After that each student can optionally hide under a bed.
- Instructors enter room 1 and room n, they count students there and lock the room (after it no one can enter or leave this room).
- Each student from rooms with numbers from 2 to n - 1 can run to another room but not further than d rooms away from her current room, or stay in place. Each student can optionally hide under a bed.
- Instructors move from room 1 to room 2 and from room n to room n - 1.
- This process continues until all rooms are processed.

Let x1 denote the number of rooms in which the first instructor counted the number of non-hidden students different from b, and x2 be the same number for the second instructor. Students know that the principal will only listen to one complaint, therefore they want to minimize the maximum of numbers xi. Help them find this value if they use the optimal strategy.

Input format:
The first line contains three integers n, d and b (2 ≤ n ≤ 100 000, 1 ≤ d ≤ n - 1, 1 ≤ b ≤ 10 000), number of rooms in the house, running distance of a student, official number of students in a room.

The second line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109), i-th of which stands for the number of students in the i-th room before curfew announcement.

It is guaranteed that a1 + a2 + ... + an = nb.

Output format:
Output one integer, the minimal possible value of the maximum of xi.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first sample the first three rooms are processed by the first instructor, and the last two are processed by the second instructor. One of the optimal strategies is the following: firstly three students run from room 5 to room 4, on the next stage two of them run to room 3, and one of those two hides under a bed. This way, the first instructor writes down room 2, and the second writes down nothing.

In the second sample one of the optimal strategies is the following: firstly all students in room 1 hide, all students from room 2 run to room 3. On the next stage one student runs from room 3 to room 4, and 5 students hide. This way, the first instructor writes down rooms 1 and 2, the second instructor writes down rooms 5 and 6.

Example input:
5 1 1
1 0 0 0 4

Example output:
1

Example input:
6 1 2
3 8 0 1 0 0

Example output:
2

Editorial:
Let's solve the problem in case when there is only one instructor (which moves from left to right and the only goal is to minimize number of bad rooms)
I claim, that the following greedy works:
• Move through rooms from left to right
• If there are too many students inside room, send the excess students to the next room
• If there are not enough students, but it is possible to fulfill this room from rooms on the right (the sum $$\sum_{j=i}^{\min(n-1,i+d*(i+1))}a_j$$ is at least b), then do it.
• If it's not possible, then send all students to the following room.
• If it is the last room, say that those students are hiding in it.
This greedy can be implemented in $${\mathcal{O}}(n)$$ time: calculate the prefix sums on the initial ai, this way you can check if it is possible to move students from following rooms here fast.
To handle the removal students from following rooms you can maintain the current "debt" of students. When you first consider room you can repay the debt as much as you can and then check one of the cases above. Since the both left and right borders of segments are moving monotonously the debt will be "inherited" correctly.
Notice, that you can only consider "paths of different students never cross", that means if first student was initially in room i and moved to a, while the second student was in j and moved to b, then if i ≤ j than a ≤ b. Because otherwise you can swap students and nothing will change.
The proof of the greedy (you can possibly skip it).
Suppose there is a better answer, which completes the rooms a1, ..., ak, while the greedy solutions completes rooms b1, ..., bl, l < k.
We will assume that in optimal solution paths of students don't intersect, that all "excessive" students are hiding in last room and that all rooms in optimal answer are either full (b) or empty (0). Otherwise it's possible to change the "correct answer in such way, that number of good rooms will not decrease.
Let's i is smallest index when ai ≠ bi. Then ai > bi, because greedy solution would always fulfill the room ai if it would be possible (actually, greedy solution builts the lexmin solution).
But if ai > bi we can "patch" the supposed optimal solution and move all students which were sent to room bi to ai (we know it is possible by the greedy solution's answer).
This way we can increase the common prefix with any possible "best" answer hence contradiction.
Back to the problem with two instructors. Recall, that "paths of different students don't cross", hence there exists a "border", the number x from 0 to nb, where the first x students are going to the first instructor and all others to second.
One could have bruteforced that border and solved the both halfs of the array by the method above, but then the complexity will be n2·b which is too much. We need to search for the border more efficiently.
Let f(m) will be the answer for first instructor, when he is given m first students and g(m) is the answer for second instructor when he is given all students except first m ones.
It is easy to see, that f(m) in decreasing, while g(m) is increasing (both times it is not strict monotonicity). Indeed, the more students are given to instructor, than more opportunities he has (all excessive students can always hide, so it is not a problem).
We are searching for m where ans(m) = max(f(m), g(m)) is smallest possible.Let's introduce function z(m) = g(m) - f(m) — increasing (but still not strict).
Let's call m0 the smallest index, such that z(m0) ≥ 0. One can see, that a min(ans(m0 - 1), ans(m0)) is the final answer. Indeed, if one will try greater m's than m0, than the g(m) will be dominating in max, and hence ans(m0) is more optimal. Otherwise, if m < m0 - 1, then ans(m) is better.
Bonus (medium): Solve this problem in O(n) time.
Bonus (medium): Students became fat and can't hide under the bed! Can you solve it now?