我的60pts和其他人的原因貌似不一样...
找不出来什么问题,求教!
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ldb long double
int n,s,t,f,tq[300010],fq[300010],dp[300010];
int l,r,qu[300010];
//dp[j]=(s+tq[i])*fq[j]+dp[i]-tq[i]*fq[i]-s*fq[n];
bool check(int mid,int k){// mid是队列中点的下标(偏左)
int a=dp[qu[mid+1]]-dp[qu[mid]];
int b=fq[qu[mid+1]]-fq[qu[mid]];
if(a>b*k) return 1;
else return 0;
}
int point(int l,int r,int k){
int lhs=l,rhs=r,mid;
if(lhs==rhs) return qu[lhs];
while(lhs<rhs){
mid=(lhs+rhs)>>1;
if(check(mid,k)==1) rhs=mid;
else lhs=mid+1;
}
return qu[lhs];
}
signed main(){
cin>>n>>s;
for(int i=1;i<=n;i++){
scanf("%d%d",&t,&f);
tq[i]=tq[i-1]+t;
fq[i]=fq[i-1]+f;
}
l=r=1; qu[1]=0;// l==r表示队列中有一个元素
for(int i=1;i<=n;i++){
int k=s+tq[i],p;// 斜率
p=point(l,r,k);// 在队列中查找斜率首个大于k的下标
dp[i]=dp[p]-(s+tq[i])*fq[p]+tq[i]*fq[i]+s*fq[n];
while(l<r){
int a=dp[i]-dp[qu[r]]; int c=dp[qu[r]]-dp[qu[r-1]];
int b=fq[i]-fq[qu[r]]; int d=fq[qu[r]]-fq[qu[r-1]];
if(a*d<=b*c) r--;
else break;
}
qu[++r]=i;
}
printf("%lld",dp[n]);
return 0;
}