题目链接

想到了如果设 $sum$ 为前缀和数组的话，答案为

$\max\limits_{1 \le i \le N}\{sum_i-\min\limits_{0 \le j < i,P \le \left|i-j+1\right| \le Q}\{sum_j\}\}$

然后用单调队列计算 $\min\limits_{0 \le j < i,P \le \left|i-j+1\right| \le Q}\{sum_j\}$。但样例输出 $-8$，求调。

#include<cstdio>
#include<deque>
using namespace std;
const int MAXN=100005;
int a[MAXN],sum[MAXN];
int main() {
  //freopen("vacation.in","r",stdin);
  //freopen("vacation.out","w",stdout);
  int n,p,q;
  scanf("%d %d %d",&n,&p,&q);
  for(int i=1;i<=n;i++) {
  	scanf("%d",&a[i]);
  	sum[i]=sum[i-1]+a[i];
  }
  int ans=-100000000,k=q-p+1;
  deque<int>que;
  for(int i=1;i<=n;i++) {
  	while(!que.empty()) {
  	  if(sum[i]>sum[que.back()])
  	    que.pop_back();
  	  else
  	    break;
  	}
  	que.push_back(i);
  	while(i-que.front()>=k)
  	  que.pop_front();
  	if(i>=k&&ans<sum[que.front()])
  	  ans=sum[que.front()];
  }
  printf("%d",ans);
  return 0;
}