题目：传送阵
思路：
分析题目，简单的说这个题目求的就是最大不定长子段和，那么首先对于最大不定长子段和，我们肯定要首先预处理前缀和数组，然后首先朴素的想，
对于以第i个元素结尾的子段，最大的子段和res为
res=max(res,sum[i]-sum[j]); j的范围是i-k到i-1
也可以简化为res=max(res,sum[i]-min_sum); min_sum指最小的sum[j]。
那么sum[i]肯定是已知的，那么我们如何在(O)m的时间复杂度求出最小的前缀和。那么现在我们就可以用一个单调队列来解决这个问题：用单调队列处理k个范围内的最小的sum[i]，然后就是个单调队列的板子题。
int hh=0,tt=-1;
ll res=-1e9;
for(int i =1;i<=m;i++)
{
if(quq[hh]<i-k)hh++;
while(tt>=hh&&sum[quq[tt]]>=sum[i])tt--;
res=max(res,sum[i]-sum[quq[hh]]);
quq[++tt]=i;
}
res初始化为最小，然后因为要减去的前缀和的 位置是i-k到i-1，那么如果队尾小于i-k时我才需要出队，然后每次找有没有比当前前缀和小的前缀和，如果有则--，然后每次遍历res最后的结果就是我的结果。
——————————————————————————————————————————
至少我认为是这样的qwq。
在洛谷中，这是没问题的，但是在计蒜客中是wa9了的（鬼知道洛谷的数据咋这么水），那么重新看这一个代码，看看有没有什么问题。
好
我不知道你发没发现，反正我发现了qwq
就是当我的n和m是相等的情况下（就是我有n个蛋糕并且能吃n个），而且这些蛋糕我都能吃，那么正常情况下是不是一个都不吃相当于减去sum[0]，但是在我的单调队列中，除了i为1的时候（因为队尾初始化就是0），其他时候的最小前缀都是sum[1]，那么我们就少了一个sum[0]的情况，于是我们手动添加一个sum[0]的前缀就可以啦。（还有一个问题就是第一个是大于0的然后其他数都是小于0的应该只取第一个也是减去sum[0]，但是因为i是1的时候刚好quq[hh]也是0所以无伤大雅。。。。）
最后代码
/**
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
#include<cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include<vector>
#include<queue>
#include<map>
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long
using namespace std;
const int N=1000000+100;
int n ,m,h;
ll s[N],sum[N],quq[N];
int main()
{
int t,k;
sc_int(m),sc_int(k);
for(int i =1;i<=m;i++){
sc_ll(s[i]);
sum[i]=sum[i-1]+s[i];
}
int hh=0,tt=-1;
ll res=-1e9;
quq[++tt]=0;
for(int i =1;i<=m;i++)
{
if(quq[hh]<i-k)hh++;
while(tt>=hh&&sum[quq[tt]]>=sum[i])tt--;
res=max(res,sum[i]-sum[quq[hh]]);
quq[++tt]=i;
}
cout<<res<<endl;
return 0;
}