ananran998 @ 2023-06-08 16:29:13
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<":"<<x<<endl
const int N = 2e5 + 1;
int n, a[N], f[N];
char s[1002];
int q[N], front = 1, rear = 0;
inline void solve() {
int L, R;
scanf("%d%d%d", &n, &L, &R);
for (int i = 0; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
f[i] = -1;
f[0] = 0;
q[++rear] = 0;
int k = 0;
for (int i = L; i <= n; i++) {
if (!(abs(q[front] - i) >= L && abs(q[front] - i) <= R))
++front;
if (front <= rear && abs(q[front] - i) >= L && abs(q[front] - i) <= R)
f[i] = f[q[front]] + a[i];
// debug(i), debug(front), debug(rear), debug(q[front]);
++k;
while (front <= rear && f[k] >= f[q[rear]])
--rear;
q[++rear] = k;
}
for (int i = n - R + 1; i <= n; i++)
f[n] = max(f[n], f[i]);
// for (int i = 1; i <= n; i++)
// printf("i : %d, f[i] : %d\n", i, f[i]);
printf("%d\n", f[n]);
}
//0 12 3 11 7 -2
/*
5 3 4
0 1 2 3 4 5
*/
int main() {
int t;
// cin >> t;
t = 1;
while (t--)
solve();
return 0;
}
// 1 5 6 7 2 10 9 8 4 3 1
by Aisaka_Taiga @ 2023-06-14 15:34:46
@ananran998 你的初始值太大了,f设为一个极小值比如-0x3f3f3f3f就过了