蒟蒻求助

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k;
ll dp[110000],sum[110000],e[110000];
struct node
{
    int pos;
    ll val;
}q[110000];
node push(ll nv,int np)
{
    node a;
    a.pos=np;
    a.val=nv;
    return a;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&e[i]);
        sum[i]=sum[i-1]+e[i];
    }
    int head=1,tail=1;
    dp[k]=sum[k];
    q[head]=push(dp[k-2]-sum[k-1],k);
    for(int i=k+1;i<=n;i++)
    {
        while(head<=tail&&q[tail].val<=dp[i-2]-sum[i-1])tail--;
        q[++tail]=push(dp[i-2]-sum[i-1],i);
        while(i-q[head].pos>=k)head++;
        dp[i]=max(dp[i-1],sum[i]+q[head].val);
    }
    printf("%lld",dp[n]);
    return 0;
}
/*dp[i]=max( max{sum[i]-sum[j-1]+dp[j-2]}(i-k+1<=j<=i) , dp[i-1] )
    相当于是找(dp[j-2]-sum[j-1])的最大值。 
*/