60 pts,qwq

P1725 琪露诺

bc2_cryeggy @ 2023-12-30 11:01:09

#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;
}

by NO_OI_NO_LIFE @ 2023-12-30 11:22:48

@beautiful_chicken233 数据范围,数组开小了


by NO_OI_NO_LIFE @ 2023-12-30 11:23:21

@beautiful_chicken233

const int kMaxN = 1e5 + 10

改成

const int kMaxN = 2e5 + 10

by NO_OI_NO_LIFE @ 2023-12-30 11:26:41

@beautiful_chicken233 另外给个小优化:

for (int i = 0; i <= n; ++ i) {

改成

for (int i = l; i <= n; ++ i) {

by NO_OI_NO_LIFE @ 2023-12-30 11:41:37

@beautiful_chicken233 长沙OIer太厉害了,六年级都会单调队列优化dp了/qiang


by bc2_cryeggy @ 2023-12-30 13:53:07

@zyh0516_lucky Thanks. 另外长沙 OIer 并非这样,我现在在雅礼中学(湖南四大名校)上 C++ 课,才这样。我朋友 @haokee 都学到网络流了。


by bc2_cryeggy @ 2023-12-30 13:56:09

@zyh0516_lucky 而且我咋觉得我很弱呢


by NO_OI_NO_LIFE @ 2023-12-30 16:36:31

@beautiful_chicken233 我说的也是相比我而言,你比我小还比我强


|