WA 60pts
查看原帖
WA 60pts
289056
北射天狼楼主2023/8/1 08:50

这题是不能把时间当成斜率吗?

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int s = 0,f = 1;char c = getchar();
	while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
	while (isdigit(c)){s = (s << 3) + (s << 1) + (c ^ 48);c = getchar();}
	return s*f;
}
const int N = 3e5 + 5;
int n,s;
int tim[N],sum[N];
int l,r;
int dp[N],q[N<<1];
int f(int x){
	return dp[x] + tim[x-1] * sum[n];
}
int search(int l,int r,int i){
	int L = l,R = r;
	int ans = 0;
	while (L <= R){
		int mid = (L + R) / 2;
		if (mid + 1 > r){
			return q[mid];
		}
		if (f(q[mid+1]) - f(q[mid]) > sum[i-1] * (tim[q[mid+1] - 1] - tim[q[mid] - 1]))
		    ans = mid,R = mid-1;
		else L = mid+1;
	}
	//cout << ans << endl;
	return q[ans];
}
signed main()
{
    n = read();s = read();
    for (int i=1;i<=n;i++){
    	tim[i] = tim[i-1] + read();
    	sum[i] = sum[i-1] + read();
	}
	l = 1,r = 1;
	q[1] = n+1;
	for (int i=n;i>=1;i--){
		int k = search(l,r,i);
	//	cout << i << " " << k << endl;
		dp[i] = dp[k] + (s + tim[k-1] - tim[i-1]) * (sum[n] - sum[i-1]); 
		while (l < r && (f(i) - f(q[r])) * (tim[q[r]-1] - tim[q[r-1]-1]) >= (f(q[r]) - f(q[r-1])) * (tim[i-1] - tim[q[r]-1]))
		    r--;
		q[++r] = i;
	}
	cout << dp[1] << endl;
	return 0;
}

2023/8/1 08:50
加载中...