题目大意：太长自己看 令个僵尸与房屋的初始距离 我们发现我们能消灭一个僵尸当且仅当 那么我们要求的显然就是 我们将一个僵尸抽象成一个点，那么我们发现每个回合僵尸之间的相对位置是不变的 因此我们可以维护一个凸包，，三分即可
;ld;struct Point{ld x,y;Point() {}Point(ld _,ld __):x(_),y(__) {}friend ld Get_Slope(const Point &p1,const Point &p2){return (p1.y-p2.y)/(p1.x-p2.x);}}O,stack[M];int top;int n;long long d,a[M],sum[M];ld ans;void Insert(const Point &p){while( top>=2 && Get_Slope(stack[top-1],stack[top]) >= Get_Slope(stack[top],p) – EPS )top–;stack[++top]=p;}ld Trisection(){int i,l=1,r=top;while(r-l>=3){int l_mid=(l+l+r)/3,r_mid=(l+r+r)/3;ld _l=Get_Slope(stack[l_mid],O);ld _r=Get_Slope(stack[r_mid],O);if(_l>_r)r=r_mid;elsel=l_mid;}ld re=0;for(i=l;i<=r;i++)re=max(re,Get_Slope(stack[i],O));return re;}int main(){int i;long long x;cin>>n>>d;for(i=1;i<=n;i++){#ifdef PoPoQQQscanf(“%I64d%I64d”,&a[i],&x);#elsescanf(“%lld%lld”,&a[i],&x);#endifsum[i]=sum[i-1]+a[i];Insert(Point(i*d,sum[i-1]));O=Point(i*d+x,sum[i]);ans+=Trisection();}cout<<fixed<<setprecision(0)<<ans<<endl;return 0;}
无论身处何处，只要有一颗放松而美好的心态，生活便是美好！
