每日AC

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> cost(n + 1);
	for (int i = 1; i <= n; ++i) {
    		cin >> cost[i];
	}

	vector<int> dp(n + 2, 0);
	deque<int> q;
	q.push_back(0);
	dp[0] = 0;

	for (int i = 1; i <= n + 1; ++i) {
    		while (!q.empty() && q.front() < i - m) {
        			q.pop_front();
    		}
    		dp[i] = dp[q.front()] + (i <= n ? cost[i] : 0);
    		while (!q.empty() && dp[i] <= dp[q.back()]) {
        			q.pop_back();
    		}
    		q.push_back(i);
	}

	cout << dp[n + 1] << endl;
	return 0;
}