斜优板子题75求调悬赏1关注
查看原帖
斜优板子题75求调悬赏1关注
221023
LuomuQDM楼主2022/10/26 14:54

如题,错的点很分散,实在找不出来哪里错了,和题解也对过了

#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;
}
2022/10/26 14:54
加载中...