PROG-T1157: Electricity

#include <iostream>
#include <queue>
using namespace std;

using pii = pair<int, int>;
using lli = long long;
const int N = 500010;

int A[N];
lli dp[N];

int main() {

    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &A[i]);
    }

    priority_queue<pii, vector<pii>, greater<pii>> Q;
    dp[1] = A[1];
    for(int i = 2; i <= n; ++i) {
        // push pop ... // dp[i] = min(dp[i-k..i-1])
        Q.push(make_pair(dp[i - 1], i - 1));
        while(!Q.empty() && Q.top().second < i - k){
            Q.pop();
        }
        dp[i] = Q.top().first + A[i];
    }

    printf("%d\n", dp[n]);

    return 0;
}