0pts求调悬关
查看原帖
0pts求调悬关
1116724
Chitose_楼主2024/2/29 15:52
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=3e5+10;
int sf[maxn],st[maxn],dp[maxn],s,a,b,ans;
int q[maxn];
int n;
double slope(int x,int y){
	return (1.0*(dp[x]-dp[y]))/(1.0*(sf[x]-sf[y]));
}

	
signed main(){
	scanf("%lld%lld",&n,&s);
	for(int i=1;i<=n;i++) {
		scanf("%lld%lld",&a,&b);
		st[i]=st[i-1]+a;
		sf[i]=sf[i-1]+b;
	}
	int l = 0,r = 0;
	for(int i=1;i<=n;i++) {
		int ll=l,rr=r;
		while(ll<rr) {	
			int mid=(ll+rr)/2;
			if(slope(q[mid],q[mid+1])<1.0*(st[i]+s)) ll=mid+1;
			else rr=mid;
		}
		ans=ll;
		dp[i]=dp[ans]+st[i]*(sf[i]-sf[ans])+s*(sf[n]-sf[ans]);
		while(r>l+1 && slope(q[r],i)<slope(q[r],q[r-1])) r--;
		q[++r]=i;
	}
	cout<<dp[n]<<endl;
	return 0;
}
2024/2/29 15:52
加载中...