【题解】

　　二分答案+差分

　　本题要求出尽量小的威力值P，很容易想到二分答案

　　而本题难点在于二分答案之后的检验。每发子弹对一个区间造成影响，我们可以尝试使用差分。但每发子弹对区间不同位置的影响是不同的。因此我们可以用多阶差分。

a3	0	-p	-p+1	-p+4	-p+9	...	-p+s2	0	0	0	0
a2	0	0	1	3	5	...	2s-1	p-s2	0	0	0
a1	0	0	1	2	2	...	2	p-(s+1)2+2	-p+s2	0	0
a0	0	0	1	1	0	...	0	p-(s+1)2	-2p+2s2+2s-1	p-s2	0

　　

1 #include
      
        2 #include
       
         3 #include
        
          4 #define LL long long 5 using namespace std; 6 const int maxn=1000010; 7 LL n,k,l,r,mid,ans,a0[maxn],a1[maxn],a2[maxn],a3[maxn],b[maxn],b2[maxn]; 8 inline LL read(){ 9     LL k=0,f=1; char c=getchar();10     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();11     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();12     return k*f;13 }14 inline LL max(LL x,LL y){
    return x>y?x:y;}15 inline LL min(LL x,LL y){
    return x
         
          k) return 0;27         a3[i]-=num*x;28         a0[i+1]+=num; a0[i+2]+=num;29         a0[min(i+stop,n)+1]+=(x-(stop+1)*(stop+1))*num;30         a0[min(i+stop,n)+2]+=(-2*x+stop*stop+(stop+1)*(stop+1)-2)*num;31         a0[min(i+stop,n)+3]-=(stop*stop-x)*num;32     }33     return cnt<=k;34 }35 int main(){36     n=read(); k=read();37     for(int i=n;i;i--) b[i]=b2[i]=read()+1,r=max(r,b[i]+1LL*(i-1)*(i-1));//先把数组倒过来，方面后面的差分 38     l=0; r<<=1;39     while(l+1
          
           >1)) r=mid; else l=mid;40     return printf("%lld\n",r),0;41 }