## Wednesday, August 27, 2014

### a bit of codeforces: 262 Div 2 Problem C - Present

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

//CODEFORCE #262 Div 2 Problem C
/*
* Given a_1, a_2, ..., a_n  , M, W
* and Operation update(i): add 1 to a_i ... a_(i+W)
* return maximum possible minimum element after M updates
*
* Solution: Binary Search + DP
* Let S[i] be the minimum updates necessary to make each element in A[1..i] >= H
* S[i+1] >= S[i], and
* S[i] - S[i-W+1] = amount of updates done in [i-W .. i] which also affect i
* Similar to 1D Sum Array, but here it is done vertically!
* You want a fast look up to know what is the total updates done in this last W elements
* Which is supplied by the 1D Sum Array in O(1)
* Illustration:
*  W = 5
*  1  4  5  9  1  9  4  2  8  1  9  S[i]  (S[i-1] - S[i-W])
*  1  1  1  1  1                       1
*     3  3  3  3  3                    4     1 - 0 = 1, add 3
*        1  1  1  1  1                 5     4 - 0 = 4, add 1
*           4  4  4  4  4              9     5 - 0 = 5, add 4
*              0  0  0  0  0           9     9 - 0 = 9, add nothing
*                 1  1  1  1  1       10     9 - 1 = 8, add 1
*                    0  0  0  0  0    10    10 - 4 = 6, add nothing
*                       0  0  0  0    10    10 - 5 = 5, add nothing
*                          7  7  7    17    10 - 9 = 1, add 7
*                             0  0    17    17 - 9 = 8, add nothing
*                                2    19    17 - 10 = 7, add 2
*/

#define NMAX 100010
typedef long long llong;

llong Height[NMAX], Sum[NMAX]; //1-indexed
int N, M, W;
llong Cur, Hi, Lo, Mid;

bool check(int Min){
for(int i=0; i<=N; ++i)
Sum[i] = 0;

for(int i=1; i<=N; ++i){
Sum[i] = Sum[i-1];

Cur = Height[i] + Sum[i-1] - Sum[ max(i-W, 0) ];
if( Cur < Min ){
Sum[i] += Min - Cur;
}
}

return Sum[N] <= M;
}

int main(){
cin >> N >> M >> W;
for(int i=1; i<=N; ++i){
cin >> Height[i];
}
Lo = 0, Hi = (llong) 1e9 + (llong) 1e5;
while ( Lo <= Hi ){
Mid = (Lo + Hi)/2;
if( check(Mid) ){
Lo = Mid + 1;
} else {
Hi = Mid - 1;
}
}
cout << Hi << endl;
return 0;
}