求卡常优化

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
int arr[1145144];
int sum[1145144];
int dp[1145144][2];
// 不取: dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
// 取  : dp[i][1]=

struct node {
    int val,ind;
    bool operator < (const node &other) const {
        return val<other.val;
    }
};
priority_queue<node> q;
int get(int i,int j) { // i<j
    return sum[j]-sum[i-1];
}
void out() {
    for(int i=1;i<=n;i++) cout<<dp[i][0]<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++) cout<<dp[i][1]<<" ";
    cout<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>arr[i];  
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+arr[i];
    q.push({0,0});
    for(int i=1;i<=n;i++) {
        while(!q.empty()) {
            if (q.top().ind<i-k) q.pop();
            else break;
        }
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        for(int j=1;j<=k;j++) {
            if (i-j+1<=0) break;
            //int tmp=(i-j>=1)?(dp[i-j][0]):0;
            //cout<<q.top().val<<endl;
            dp[i][1]=max(dp[i][1],sum[i]+q.top().val);//sum[i]-sum[i-j]
        }
        q.push({dp[i][0]-sum[i],i});
    }
    //out();
    cout<<max(dp[n][0],dp[n][1]);
}