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 我说的也是相比我而言,你比我小还比我强