求助
查看原帖
求助
778022
yhylivedream楼主2024/5/30 07:03
//author : yhy
#include <bits/stdc++.h> 

using namespace std;
using LL = long long;
using Pii = pair<LL, LL>;

const LL kMaxN = 3e5 + 5;

LL n, s, h = 1, t = 1, f[kMaxN], q[kMaxN], pret[kMaxN], prec[kMaxN];

signed main() {
  cin.tie(0)->ios::sync_with_stdio(0), cin >> n >> s;
  for (LL i = 1, t, c; i <= n; i++) {
    cin >> t >> c, pret[i] = pret[i - 1] + t, prec[i] = prec[i - 1] + c;
  }
  for (LL i = 1; i <= n; i++) {
    for (; h < t && f[q[h + 1]] - f[q[h]] <= 
                    (s + pret[i]) * (prec[q[h + 1]] - prec[q[h]]); h++) {
    }
    f[i] = f[q[h]] - (s + pret[i]) * prec[q[h]] + pret[i] * prec[i] + s * prec[n];
    for (; h < t && (f[q[t]] - f[q[t - 1]]) * (prec[i] - prec[q[t]]) <= 
                    (f[i] - f[q[t]]) * (prec[q[t]] - prec[q[t - 1]]); t--) {
    }
    q[++t] = i;
  }
  cout << f[n];
}

只有第 8 个点A了。

2024/5/30 07:03
加载中...