大佬求条

📅 2026/7/24 15:49:48 👁️ 阅读次数 📝 编程学习
大佬求条

include<bits/stdc++.h>

using namespace std;

define maxn 300100

define int long long

int q[maxn*2],l=maxn-100,r=maxn-100;
int n,s,t[maxn],f[maxn],dp[maxn],pret[maxn],pref[maxn];
signed main(){

cin>>n;
cin>>s;
for(int i=1;i<=n;i++){
cin>>t[i]>>f[i];
}
for(int i=1;i<=n;i++){
pret[i]=pret[i-1]+t[i];
pref[i]=pref[i-1]+f[i];
}
q[--l]=0;
q[++r]=1;
dp[0]=0;
dp[1]=spref[n]+t[1]f[1];

for(int i=2;i<=n;i++){
int kn=(s+pret[i]);
int ln=l,rn=r;
while(ln<rn){
int mid=(ln+rn)/2;
if((__int128)((dp[q[mid+1]]-dp[q[mid]]))<=(__int128)(knpref[q[mid+1]]-pref[q[mid]])){
ln=mid+1;
}
else{
rn=mid;
}
}
int jn=q[ln];
dp[i]=dp[jn]+pret[i]
(pref[i]-pref[jn])+(pref[n]-pref[jn])*s;

while(r-l+1>1&&(__int128)((dp[i]-dp[q[r]])(pref[q[r]]-pref[q[r-1]]))<=(__int128)((pref[i]-pref[q[r]])(dp[q[r]]-dp[q[r-1]])))r--;
q[++r]=i;
}
cout<<dp[n];
return 0;
}