惊了，我怎么这么菜啊。。
题目链接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=3203
(luogu)https://www.luogu.org/problemnew/show/P3299
题解: 先讲正常做法。
设(S_i)为(i)的前缀和，则显然第(i)次答案为(max^i_{j=1} frac{S_i-S_{j-1}}{x_i+id-jd})
那么很显然就是要求从一个点((x_i+id,S_i))到((jd,S_{j-1}))的斜率最大值啊。。三分凸壳就行了啊。。想什么呢。。。
下面是我的垃圾做法，有兴趣的可以感受一下（我相信没人有兴趣）
考虑斜率优化(我就是陷入套路无法自拔的垃圾)，首先为了方便我们把输入的(x_i)加上(id)并记作(x_0), 目前的总和记作(S), (1)到((i-1))的和记作(S_i)(和上面定义不同)，考虑(i)不比(j)差((i<j))的条件: $$frac{S-S_i}{x_0-id}>frac{S-S_j}{x_0-jd}$$展开后解得$$x_0gefrac{iS-jS-iS_j+jS_i}{S_j-S_i}d$$考虑三个点(i<j<k), (i)不比(j)劣的条件是$$x_0gefrac{iS-jS-iS_j+jS_i}{S_j-S_i}d$$ (k)不比(j)劣的条件是$$x_0lefrac{jS-kS-jS_k+kS_j}{S_k-S_j}d$$若后者大于等于前者则无论(x_0)为何值此两个条件至少满足一个，(j)无用。
然后尝试化这个式子: $$frac{jS-kS-jS_k+kS_j}{S_k-S_j}ge frac{iS-jS-iS_j+jS_i}{S_j-S_i}$$ $$iS_jS_k-iS_j^2-jS_iS_k+jS_iS_j+jSS_k-jSS_j-iSS_k+iSS_jle jS_kS_j-jS_iS_k-kS_j^2+kS_iS_j+kSS_j-kSS_i-jSS_j+jSS_i$$ $$(i-j)S_jS_k+(k-i)S_j^2+(j-k)S_iS_j+(j-i)SS_k+(i-k)SS_j+(k-j)SS_ile 0$$ 尝试因式分解 $$(S_j-S)(iS_k-jS_k+kS_j-iS_j+jS_i-kS_i)le 0$$ 因为(S_j-S)显然小于(0), 所以$$iS_k-jS_k+kS_j-iS_j+jS_i-kS_ige 0$$ 这个东西一看就是可以拆添项的: $$iS_k-jS_k+kS_j-jS_j-iS_j+jS_j+iS_k-jS_kle 0$$ $$(j-k)(S_i-S_j)-(i-j)(S_j-S_k)le 0$$ $$frac{S_i-S_j}{i-j}le frac{S_j-S_k}{j-k}$$
这是(j)无用的条件，所以只需要维护斜率不增的上凸壳即可
……
我真的蠢到一定境界了
代码
当然是我的垃圾做法的代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
#define llong long long
using namespace std;
struct Point
{
double x,y;
Point() {}
Point(llong _x,llong _y) {x = _x,y = _y;}
};
const int N = 1e5;
Point ch[N+3];
double s[N+3];
double a[N+3];
double qr[N+3];
int n,tp;
double d;
void insertpoint(Point x)
{
while(tp>1 && (ch[tp].y-ch[tp-1].y)*(x.x-ch[tp].x)>=(x.y-ch[tp].y)*(ch[tp].x-ch[tp-1].x)) {tp--;}
tp++; ch[tp] = x;
// printf("CH: size=%d ",tp);
// for(int i=1; i<=tp; i++) printf("(%lf %lf) ",ch[i].x,ch[i].y); puts("");
}
double query(double x,double sum)
{
// printf("query(%lf %lf)
",x,sum);
int left = 1,right = tp;
while(left<right)
{
int mid = (left+right+1)>>1;
bool ok = x*(ch[mid].y-ch[mid-1].y)<=(ch[mid-1].x*ch[mid].y-ch[mid].x*ch[mid-1].y+ch[mid].x*sum-ch[mid-1].x*sum)*d ? true : false;
if(ok) {left = mid;}
else {right = mid-1;}
}
// printf("left=%d
",left);
double ret = (sum-ch[left].y)/(x-ch[left].x*d);
return ret;
}
int main()
{
scanf("%d%lf",&n,&d);
for(int i=1; i<=n; i++)
{
scanf("%lf%lf",&a[i],&qr[i]);
s[i] = s[i-1]+a[i-1];
qr[i] += i*d;
}
s[n+1] = s[n]+a[n];
double sans = 0.0;
for(int i=1; i<=n; i++)
{
insertpoint(Point(i,s[i]));
double ans = query(qr[i],s[i+1]);
sans += ans;
// printf("i%d ans%lf
",i,ans);
}
printf("%lld
",(llong)(sans+0.5));
return 0;
}