这题是不能把时间当成斜率吗?
#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;
}