60 pts,qwq
查看原帖
60 pts,qwq
814343
bc2_cryeggy楼主2023/12/30 11:01
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;

const int kMaxN = 1e5 + 10, kInf = (((1 << 30) - 1) << 1) + 1;

int n, l, r, a[kMaxN];
ll f[kMaxN], maxa = -1e18;
deque<int> q;

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> l >> r;
  for (int i = 0; i <= n; ++ i) {
    cin >> a[i];
  }
  for (int i = 1; i < l; ++ i) {
    f[i] = -1e18;
  }
  for (int i = 0; i <= n; ++ i) {
    for (; i - l && !q.empty() && f[q.back()] < f[i - l]; q.pop_back());
    if (!q.empty() && i - r > q.front()) {
      q.pop_front();
    }
    if (i - l >= 0) {
      q.push_back(i - l);
    }
    if (!q.empty()) {
      f[i] = f[q.front()] + a[i];
    }
    if (i + r > n) {
      maxa = max(maxa, f[i]);
    }
  } 
  cout << maxa << '\n';
  return 0;
}
2023/12/30 11:01
加载中...