CE代码求调,不知道怎么错的
查看原帖
CE代码求调,不知道怎么错的
1303372
Michael_114楼主2024/10/9 21:59
#include<bits/stdc++.h>  
using namespace std;
typedef long long ll;
#define maxn 300000+10
ll q[maxn];
ll head = 1,tail = 0,n,s;
ll sc[maxn],st[maxn],f[maxn];
int find(int l,int r,ll s){
	int m = 0,ans = tail;
	while(l<=r){
		m = (l+r)/2;
		if(f[q[m+1]]-f[q[m]]>s*(sc[q[m+1]]-sc[q[m]])){
			r = m-1,ans = m;
		}else{
			l = m+1;
		}
	}
	return q[ans];
}
int main() {
	cin>>n>>s;
	for(int i= 1;i<=n;i++){
		cin>>st[i]>>sc[i];
		st[i]+=st[i-1];
		sc[i]+=sc[i-1];
	}
	q[++tail] = 0;
	for(int i = 1;i<=n;i++){
		int p = find(head,tail,s+st[i]);
		f[i] = f[p]+s*(sc[n]-sc[p])+st[i]*(sc[i]-sc[p]);
		while(head<tail&&
		(f[q[tail]]-f[q[tail-1]])*(sc[i]-sc[q[tail]])
		>=(f[i]-f[q[tail]])*(sc[q[tail]]-sc[q[tail-1]])){
			tail--;
		}
		q[++tail] = i;
	}
	cout<<f[n];
	return 0;
}

CE记录

2024/10/9 21:59
加载中...