好像是二分部分错了,但一直调不出来。
#include<bits/stdc++.h>
#define MAXN 300005
#define LL long long
using namespace std;
LL n,s;
LL t[MAXN],f[MAXN];
LL sf[MAXN],st[MAXN];
LL dp[MAXN];
LL q[MAXN];
int h=1,l=1;
LL up(int j,int k){
return (f[j]-f[k]);
}
LL down(int j,int k){
return (sf[j]-sf[k]);
}
int main()
{
cin>>n>>s;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&t[i],&f[i]);
st[i]=st[i-1]+t[i];
sf[i]=sf[i-1]+f[i];
}
for(int i=1;i<=n;i++){
int j=q[h];
int L=h+1,R=l;
while(L<=R){
int mid=(L+R)/2;
if(up(q[mid],q[mid-1])<=(st[i]+s)*down(q[mid],q[mid-1]))
{
j=q[mid];
L=mid+1;
}
else R=mid;
}
dp[i]=dp[j]+(st[i]*(sf[i]-sf[j])+s*(sf[n]-sf[j]));
while(h<l&&up(i,q[l])*down(q[l],q[l-1])<=up(q[l],q[l-1])*down(i,q[l])) l--;
q[++l]=i;
}
cout<<dp[n];
return 0;
}