hack过不去,求指点
查看原帖
hack过不去,求指点
660776
ananran998楼主2023/6/8 16:29
#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
2023/6/8 16:29
加载中...