P5844 [IOI 2011] ricehub

In the countryside, there is a straight and long road called the “Rice Road”. Along this Rice Road there are $R$ rice fields, and the coordinate of each field is an integer between $1$ and $L$ (including $1$ and $L$). These fields are given in non-decreasing order of coordinates, that is, for $0 \le i < R$, the coordinate $X[i]$ of field $i$ satisfies $1 \le X[0] \le \cdots \le X[R-1] \le L$. Note: multiple fields may be located at the same coordinate. We plan to build a rice hub to store as much rice as possible. Like the rice fields, the hub will be built on the Rice Road, and its coordinate is also an integer between $1$ and $L$ (including $1$ and $L$). The hub can be built at any position that satisfies the above conditions, including positions where one or more rice fields already exist. During harvest season, each rice field produces exactly one full truckload of rice. To transport this rice to the hub, we need to hire a truck driver. The driver charges $1$ yuan per unit distance for each full truckload. In other words, the cost to transport rice from a particular field to the hub equals the absolute difference between the field’s coordinate and the hub’s coordinate. Unfortunately, this year the budget is limited, and we can spend at most $B$ yuan on transportation. Your task is to help us find a hub location that can collect as much rice as possible.

The first line contains three integers $R, L, B$. The next $R$ lines each contain one integer, representing $X[i]$.

Output one integer, the maximum amount of rice that can be collected.

For $100\%$ of the testdata, $1 \le R \le 10^5$, $1 \le L \le 10^9$, $0 \le B \le 2 \times 10^{15}$. Translated by ChatGPT 5