Contents

# subject

# Analysis

First, let’s take a look at the data range of this problem. The amount of data in Subtask 4 is 10^15 to a surprising extent. Obviously, this is the amount of data that we can not handle. But looking at the size of R is acceptable, so it is not hard to imagine that there is a discretization idea.

Then we think about how to arrange the rice barn. This rice bin is actually equivalent to a “median”, which is arranged in the middle of the section which can be processed by the rice bin.

Here is the concept of “interval”, so we can think of a similar two point idea to enumerate the left and right boundaries of the interval.

First, O (R) enumerates the left border, then inserting a while to check the right boundary, and writing a check function to check the feasibility of the interval. Check is actually using a prefix to calculate the amount of money, and then compared with the budget, return to true or false.

# Card point

Here is a small card point that is data type. At the beginning, we opened the int type, but when we think about the amazing amount of 10^15 that we saw before, it is necessary to open long long.

# program

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 100000 + 10; 4 long long S[MAXN], R, x[MAXN], r, b, ans, t; 5 bool check(int Left, int Right) 6 { 7 int hub_pos = (Left + Right) >> 1; 8 long long Cost=1ll*x[hub_pos]*(hub_pos-Left+1)-S[hub_pos]+S[Left-1]+S[Right]-S[hub_pos]-1ll*x[hub_pos]*(Right-hub_pos); 9 if (Cost <= b) 10 return true; 11 return false; 12 } 13 int main() 14 { 15 freopen("ricehub.in","r",stdin); 16 freopen("ricehub.out","w",stdout); 17 cin >> r >> t >> b; 18 for (int i = 1; i <= r; i++) 19 { 20 cin >> x[i]; 21 S[i] = S[i-1] + x[i]; 22 } 23 R = 1; 24 for (int L = 1; L <= r; L++) 25 { 26 while (R <= r && check(L,R)) 27 R++; 28 ans = max(ans, R-L); 29 } 30 cout << ans << endl; 31 return 0; 32 }