electriccity.cpp

#include<cstdio>
#include<queue>
using namespace std;
struct container
{
    int a;
    int b;
};
bool operator<(container a,container b)
{
    return a.a>b.a;
}
container container_maker(int a,int b)
{
    container ret;
    ret.a=a;
    ret.b=b;
    return ret;
}
int main()
{
    int n,k;
    priority_queue<container> pq;
    scanf("%d %d",&n,&k);
    int *arr=new int[n];
    int *dp=new int[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
        dp[i]=arr[i];
        while(!pq.empty() && i-pq.top().b>k)pq.pop();
        if(i)dp[i]+=dp[pq.top().b];
        pq.push(container_maker(dp[i],i));
//        printf("%d = %d\n",i,dp[i]);
    }
    printf("%d",dp[n-1]);
}