0分求救
查看原帖
0分求救
1087986
didi2012楼主2024/1/6 13:01
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300010;
long long q[maxn], head = 1, tail = 0, n, s, Sc[maxn], St[maxn], f[maxn];

long long find(long long L, long long R, long long S) {
	long long 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;
}
2024/1/6 13:01
加载中...