如题,错的点很分散,实在找不出来哪里错了,和题解也对过了
#include<bits/stdc++.h>
#define ll long long
#define N 300010
using namespace std;
inline ll read(){
char c=getchar();ll ans=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
return ans*f;
}
ll n,s,t,f,dp[N],mt[N],mf[N];
ll st[N],h;
ll X(ll id){
return mf[id];
}
ll Y(ll id){
return dp[id];
}
ll bs(ll k){
ll l=1,r=h,mid;
while(l<r){
mid=(l+r)>>1;
if(Y(st[mid+1])-Y(st[mid])<(X(st[mid+1])-X(st[mid]))*k)l=mid+1;
else r=mid;
}
return st[l];
}
signed main(){
n=read(),s=read();
for(ll i=1;i<=n;i++){
t=read(),f=read();
mt[i]=mt[i-1]+t,mf[i]=mf[i-1]+f;
}
dp[0]=0,st[++h]=0;
for(ll i=1;i<=n;i++){
ll j=bs(s+mt[i]);
dp[i]=dp[j]+mt[i]*(mf[i]-mf[j])+s*(mf[n]-mf[j]);
while(h>1&&(Y(st[h])-Y(st[h-1]))*(X(i)-X(st[h]))>(Y(i)-Y(st[h]))*(X(st[h])-X(st[h-1])))h--;
st[++h]=i;
}
printf("%lld\n",dp[n]);
return 0;
}