RT,我遇到蜜汁RE
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+13;
int n,s;
ll c[N],t[N];//sumc,sumt
ll f[N],q[N];
int main(){
cin>>n>>s;
for(int i=1;i<=n;i++){
cin>>t[i]>>c[i];
t[i]+=t[i-1];
c[i]+=c[i-1];//处理前缀和
}
int hh=0,tt=0;
q[0]=0;//f(0)点
for(int i=1;i<=n;i++){
//删去该线下方,斜率比该线小的线(点)
while(hh<tt&&(f[q[hh+1]]-f[q[hh]])<=(t[i]+s)*(c[q[hh+1]]-c[q[hh]])) hh++;
//上面这是处理一下斜率,防止精度挂掉
//这里直接拿来用q[hh],是因为q[hh]是凸包中不小于当前线斜率的线的左端点
int j=q[hh];
f[i]=f[j]-(t[i]+s)*c[j]+t[i]*c[i]+s*c[n];//见式,不解释
//删去此前的线(点),维护凸包性质
while(hh<tt&&(f[q[tt]]-f[q[tt-1]])*(c[i]-c[q[tt]])>=(f[i]-f[q[tt]])*(c[q[tt]-c[q[tt-1]]])) tt--;
//上面这是处理一下斜率,防止精度挂掉
q[++tt]=i;
}
cout<<f[n]<<endl;
return 0;
}
救救孩子……