题
OvO http://codeforces.com/contest/954/problem/G
解
二分答案，
对于每个二分的答案值 ANS，判断这个答案是否可行。
记 s 数组为题目中描述的 a 数组
以下为初始化：
首先建一个 pre 数组， pre[i] 表示 s 数组中第 1 个元素到第 i 个元素的和
然后建一个 p 数组，其中 p[i] 代表能射到第 i 个区域的弓箭手数量， p[i] 显然可以由 pre 计算得到
以下是对于二分的每个答案值 ANS，判断这个值是否可行的做法：
创建一个 d 数组， d[i] = p[i] - p[i-1]，
从左到右枚举 d 数组，用变量 now 累加得到当前区域的坚固程度（即能有多少弓箭手能射到这个块）
枚举的过程中，如果出现 now 比 ANS 值小的话，则得到这个差值， 记这个差值为 tmp ，那么显然要在 i+r 的地方放 tmp 个弓兵，那么要做如下操作
1. now+=tmp （则当前节点的坚固程度+tmp）
2.d[i+2*r+1)]-=tmp （区域 [i,i+2*r] 的坚固程度均加 tmp，等价的就是 1,2 这两个操作）
3.记总的可用弓兵消耗为为 cst ，则 cst+=tmp
如果 cst>k 显然不行，否则可行。
注意数据范围，容易中间爆 long long 之类的，用线段树时间大概不够（吧）
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll M=11e5+44;
const ll INF=4e18+44;
ll n,r;
ll s[M];
ll k;
ll p[M],pre[M],d[M];
bool check(ll spl)
{
ll cst=0,now=0,tmp;
for(ll i=1;i<=n;i++)
d[i]=p[i]-p[i-1];
for(ll i=1;i<=n;i++)
if((now+=d[i])<spl)
{
tmp=spl-now;
if((cst+=tmp)>k) return false;
d[i]+=tmp,now+=tmp,d[min(n+1,i+2*r+1)]-=tmp;
}
return true;
}
ll solve()
{
ll ret;
ll li,ri,mid;
li=0,ri=INF;
while(li<ri-1)
{
mid=((li+ri)>>1);
if(check(mid)) li=mid;
else ri=mid;
}
return ret=li;
}
int main()
{
ll li,ri;
scanf("%I64d%I64d%I64d",&n,&r,&k);
for(ll i=1;i<=n;i++)
scanf("%I64d",&s[i]);
memset(pre,0,sizeof(pre));
memset(p,0,sizeof(p));
for(ll i=1;i<=n;i++)
pre[i]=pre[i-1]+s[i];
for(ll i=1;i<=n;i++)
{
li=i-r,ri=i+r;
if(li<1) li=1;
if(ri>n) ri=n;
p[i]=pre[ri]-pre[li-1];
}
printf("%I64d
",solve());
return 0;
}