蜜汁UKE
  • 板块P1725 琪露诺
  • 楼主TRZ_2007
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/8/2 15:22
  • 上次更新2023/11/6 21:30:34
查看原帖
蜜汁UKE
86971
TRZ_2007楼主2020/8/2 15:22
#include <bits/stdc++.h>
using namespace std;

const int N = 200009;

int a[N],n,l,r;
int f[N],q[N],ans = INT_MIN;
int head = 1,tail;

void pop(int id) {
	while(head <= tail) {
		if(q[head] + r < id) head++;
		else break;
	}
}

void push(int id) {
	while(head <= tail) {
		if(f[id] >= f[q[tail]]) tail--;
		else break;
	}
	q[++tail] = id;
}

int main() {
	scanf("%d %d %d",&n,&l,&r);
	for(int i = 0;i <= n;i++) {
		scanf("%d",&a[i]);
		f[i] = -19260817;
	}
	f[0] = 0;
	for(int i = l;i <= n;i++) {
		push(i - l);
		pop(i);
		f[i] = f[q[head]] + a[i];
	}
	for(int i = n - r + 1;i <= n;i++) ans = max(ans,f[i]);
	printf("%d\n",ans);
	return 0;
}
2020/8/2 15:22
加载中...