洛谷过了,AcWing不过求调
查看原帖
洛谷过了,AcWing不过求调
999274
CNS_5t0_0r2楼主2023/12/14 13:40
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 9;
int n,s;
int t,f;
int s_t[N],s_f[N];
int dp[N];
int que[N];
int head = 1,tail;
int bnsearch(int l,int r,int k){
	int mid = 0,pos = r;
	while(l <= r){
		mid = (l + r) >> 1;
		if(dp[que[mid + 1]] - dp[que[mid]] > k * (s_f[que[mid + 1]] - s_f[que[mid]])){
			r = mid - 1;
			pos = mid;
		}
		else
			l = mid + 1;
	}
	return que[pos];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> s;
	for(int i = 1;i <= n;i++) {
		cin >> t >> f;
		s_t[i] = s_t[i - 1] + t;
		s_f[i] = s_f[i - 1] + f;
	}
	que[++tail] = 0;
	for(int i = 1;i <= n;i++){
		int pos = bnsearch(head,tail,s + s_t[i]);
		dp[i] = dp[pos] + s * (s_f[n] - s_f[pos]) + s_t[i] * (s_f[i] - s_f[pos]);
		while(head < tail && 
			(dp[que[tail]] - dp[que[tail - 1]]) * (s_f[i] - s_f[que[tail]])
			>= 
			(dp[i] - dp[que[tail]]) * (s_f[que[tail]] - s_f[que[tail - 1]]))
			tail--;
		que[++tail] = i;
	}
	cout << dp[n];
	return 0;
}
2023/12/14 13:40
加载中...