积木大赛

题解：

考试时写了一个贪心，每次在最高的能放的地方放。虽然没有证明，但似乎可以水过答案，最后得70分，剩下30分为TLE。

我们发现，如果不断垒高积木，最后是一个金字塔的形状。

（图片来源网络）

即使最后的积木形状不像一个金字塔，但它一定包含了金字塔的一部分。

观察上图，灰色块为原块，红色块为假象块，绿色块为我们要添加的块。要求得绿色部分的方块数，

可以用大金字塔的方块数 - 黄色三角形方块数 - 紫色三角形方块数 - 棕色区域方块数，设大金字塔的高为X，黄三角形坐标为L，紫三角形坐标为R。

则大金字塔的方块数 = X * X  黄色三角形方块数 = A *（A＋１）／２（等差数列）紫色三角形方块数＝B *（ B＋１）／２          棕色区域方块数可以用前缀和算出，其中三角形边长A = 二分高度 - （当前高度 - L），B同理。

然后二分答案。对于一个高度，我们检查用给定数量的方块能否达到那个高度。首先预处理出合法的L和R，可以发现H[L]具有单调性，从n枚举到1，H[L] < 二分高度 - (枚举X - L)时缩小L，满足条件时保存下来。

然后再1到n枚举X，计算出所用的方块，与m比较，若小于m则返回true。

代码：
 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define MAXA 100005
using namespace std;
typedef long long LL;
int n,m,Sum,Temp,Ans,MAXH,pos,H[MAXA],Left,Right,Mid,TempL[MAXA],TempR[MAXA];
LL Pre[MAXA];
bool Check(int NowH) {
	int L = n,R = 1;
	for(int i=n;i>=1;i--) {
		while(H[L] < NowH - (i - L) && L >= 1)
			L--;
		TempL[i] = L;
	}
	for(int i=1;i<=n;i++) {
		while(H[R] < NowH - (R - i) && R <= n)
			R++;
		TempR[i] = R;
	}
	for(int i=1;i<=n;i++) {
		if(TempR[i] > n || TempL[i] < 1) continue;
		LL Big = (LL)NowH * (LL)NowH;
		LL TriL = (LL)(NowH - (i - TempL[i]) + 1) * (LL)(NowH - (i - TempL[i])) / (LL)2;
		LL TriR = (LL)(NowH - (TempR[i] - i) + 1) * (LL)(NowH - (TempR[i] - i)) / (LL)2;
		if(Big - TriL - TriR - (Pre[TempR[i]-1] - Pre[TempL[i]]) <= (LL)m) return true;
	}
	return false;
}
int main() {
//	freopen("block.in","r",stdin);
//	freopen("block.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%d",&H[i]);
		MAXH = max(MAXH,H[i]);
		Pre[i] = Pre[i-1] + 1LL * H[i];
	}
	Left = MAXH + 1,Right = (int)(sqrt(m) + 1.00) + MAXH + 1;
	while(Left < Right) {
		Mid = (Left + Right) / 2;
		if(Check(Mid)) {
			Left = Mid + 1;
		}
		else Right = Mid;
	}
	printf("%d",Left - 1);
}