BOJ 5977 Mowing the Lawn

개요

BOJ 5977 Mowing the Lawn

• 백준 온라인 저지 5977번 문제
• BOJ 47단계

C++

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

int N, K;
typedef long long ll;
ll E[100011];
ll dp[100011]; 
ll esum[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(esum[N] + dp[i], answer);
    }
    cout << answer;
}

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