Description：

植物大战僵尸每一关都会在队头新加一个僵尸并改变改变对头位置，每一关都可以换不同攻击力的豌豆射手，问攻击力总和的最小值是多少。

$1\leqslant n\leqslant 10^5$

Solution：

设 $f[i]$ 表示第 $i$ 关所用的豌豆射手，那么有： $$ f[i]=\max_{p=1}^i(\frac{sum[i]-sum[p-1]}{d\times(i-p)+x_i}),ans=\sum_{i=1}^n f[i] $$ 那么： $$ f[i]=\max_{p=1}^i(\frac{sum[i]-sum[p-1]}{d\times i+x_i-d\times p}) $$ 可以看成是定点 $(d\times i+x_i,sum[i])$ 向 $(d\times p,sum[p-1])$ 的最大斜率，因此我们求出凸包之后三分就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

typedef long long ll;

ll d;

#define MAXN 100010

struct point

{

	ll x,y;

}p[MAXN];

ll sum[MAXN];

double f[MAXN];

point stack[MAXN];

int top = 0;

double slope(point a,point b){return 1.0 * (a.y - b.y) / (a.x - b.x);}

int main()

{

	scanf("%d%lld",&n,&d);

	ll a,x;

	double ans = 0;

	for(int i = 1;i <= n;++i)

	{

		scanf("%lld%lld",&a,&x);

		sum[i] = sum[i - 1] + a;

		p[i].x = d * i;

		p[i].y = sum[i - 1];

		while(top >= 2 && slope(stack[top - 1],stack[top]) >= slope(stack[top],p[i]))--top;

		stack[++top] = p[i];

		int l = 1,r = top,midl,midr;

		point t = (point){d * i + x,sum[i]};

		while(l <= r)

		{

			int len = (r - l + 3) / 3;

			midl = l + len - 1;midr = r - len + 1;

			double ansl = slope(t,stack[midl]);

			double ansr = slope(t,stack[midr]);

			f[i] = max(f[i],max(ansl,ansr));

			if(ansl > ansr)r = midr - 1;

			else l = midl + 1;

		}

		ans += f[i];

	}

	printf("%.0lf\n",ans);

	return 0;

}