代码如下,求助, 感谢
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
struct Opt{
int l, r, id;
};
ll c[N], t[N], s, f[N];
int n;
ll F(int i, int j){
return (f[j] + t[i]*(c[i] - c[j]) + s*(c[n] - c[j]));
}
struct Que{
Opt q[N];
int l, r;
void Clear(){
l = 1, r = 1;
q[1] = {1, n, 0};
}
void Insert(int id){
while(l <= r && F(q[r].l, q[r].id) >= F(q[r].l, id)) r--;
if(l > r){
l = r = 1;
q[1] = {1, n, id};
return ;
}
int a = q[r].l, b = q[r].r, mid = 0, res = -1;
while(a <= b){
mid = (a + b) >> 1;
if(F(mid, q[r].id) >= F(mid, id)) b = mid - 1, res = mid;
else a = mid + 1;
}
q[r].r = res - 1;
q[++r] = {res, n, id};
}
int Find(int pos){
int a = l, b = r, mid, res = -1;
while(a <= b){
mid = (a + b) >> 1;
if(q[mid].l <= pos) a = mid + 1, res = q[mid].id;
else b = mid - 1;
}
return res;
}
} q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for(int i = 1; i <= n; i++){
cin >> t[i] >> c[i];
t[i] += t[i - 1];
c[i] += c[i - 1];
}
f[0] = 0;
q.Clear();
for(int i = 1; i <= n; i++){
int cur = q.Find(i);
f[i] = F(i, cur);
q.Insert(i);
}
cout << f[n];
return 0;
}