35pts求助
查看原帖
35pts求助
406941
Register_int-std=c++14楼主2022/8/17 16:44

rt.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXN = 3e5 + 10;

int n;

ll s, dp[MAXN], t[MAXN], c[MAXN];

inline 
ll k(int p) {
	return t[p] + s;
}

inline 
ll b(int p) {
	return dp[p] - t[p] * c[p] - s * c[n];
}

inline 
ll x(int p) {
	return c[p];
}

inline 
ll y(int p) {
	return dp[p];
}

inline 
ld slope(int p, int q) {
	return (ld)(y(p) - y(q)) / (x(p) - x(q));
}

int q[MAXN << 1], tot; 

inline 
int bound(int l, int r, ld x) {
	int mid, res = r + 1;
	while (l <= r) {
		mid = l + r >> 1;
		if (slope(q[mid], q[mid + 1]) >= x) r = mid - 1, res = mid;
		else l = mid + 1;
	}
	return q[res];
}

int main() {
	scanf("%d%lld", &n, &s);
	for (int i = 1; i <= n; i++) scanf("%lld%lld", &t[i], &c[i]), t[i] += t[i - 1], c[i] += c[i - 1];
	for (int i = 1, p; i <= n; i++) {
		p = bound(0, tot - 1, k(i));
		dp[i] = dp[i] - k(i) * x(p) - b(i) + y(p);
		while (tot && slope(q[tot - 1], q[tot]) >= slope(q[tot], i)) tot--;
		q[++tot] = i;
	}
	printf("%lld", dp[n]);
}
2022/8/17 16:44
加载中...