95 pts 求调
查看原帖
95 pts 求调
648755
Full_Speed楼主2024/9/20 19:54
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e5+10;
LL n,s,t[N],c[N],dp[N],sumt[N],sumc[N];
struct line{
	LL k,b;
}d[N];
int top;
LL sctx(line a,line b){
	return (b.b-a.b)/(a.k-b.k);
}
LL Get(LL x){
	LL l=1,r=top,mid,L,R;
	while(l<r){
		mid=l+r>>1;
		L=mid==1?-2e16:sctx(d[mid],d[mid-1]);
		R=mid==top?2e16:sctx(d[mid],d[mid+1]);
		if(R<x)l=mid+1;
		else if(L>x)r=mid-1;
		else l=r=mid;
	}
	return d[r].k*x+d[r].b;
}
void add(line l){
	if(top&&l.k==d[top].k){
		if(l.b>=d[top].k)top--;
		else return;
	}
	if(top<2)goto add;
	while(top>=2){
		LL x=sctx(d[top],d[top-1]),y=sctx(l,d[top]);
		if(y<=x)top--;
		else break;
	}
	add:d[++top]=l;
}
int main(){
	scanf("%lld%lld",&n,&s);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&t[i],&c[i]);
		sumt[i]=sumt[i-1]+t[i];
		sumc[i]=sumc[i-1]+c[i];
	}
	add(line{0,0});
	for(int i=1;i<=n;i++){
		dp[i]=-Get(s+sumt[i])+s*sumc[n]+sumt[i]*sumc[i];
		add(line{sumc[i],-dp[i]});
	}
	printf("%lld",dp[n]);
	return 0;
}
2024/9/20 19:54
加载中...