BOJ 5977 Mowing the Lawn

1 개요

BOJ 5977 Mowing the Lawn
2 C++

#include <bits/stdc++.h>
using namespace std;

int N, K;
typedef long long ll;
ll E[100011];
ll dp[100011]; 
ll psum[100011];

void solve() {
    deque<pair<ll, ll>> dq;
    dq.push_back({0, 0});
    for (int i = 1; i <= N; i++) {
        while (dq.size() && dq.front().second < i - K - 1) {
            dq.pop_front();
        }
        dp[i] = dq.front().first - E[i];
        while (dq.size() && dq.back().first < dp[i]) {
            dq.pop_back();
        }
        dq.push_back({dp[i], i});
    }
    ll answer = -1e18;
    for (int i = N - K; i <= N; i++) {
        answer = max(psum[N] + dp[i], answer);
    }
    cout << answer;
}

int main() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> E[i];
        psum[i] = psum[i - 1] + E[i];
    }
    solve();
}