BOJ 15678 연세워터파크

1 개요

BOJ 15678 연세워터파크

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

2 C++

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

typedef long long ll;
int N, D;
ll K[100005];
ll dp[100005];

void solve() {
    ll answer = K[0];
    dp[0] = K[0];
    deque<int> window;
    window.push_back(0);
    for (int i = 1; i < N; ++i) {
        while (!window.empty() && window.front() < i - D) {
            window.pop_front();
        }
        dp[i] = max(K[i], dp[window.front()] + K[i]);
        while (!window.empty() && dp[window.back()] <= dp[i]) {
            window.pop_back();
        }
        window.push_back(i);
        answer = max(answer, dp[i]);
    }
    cout << answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> D;
    for (int i = 0; i < N; ++i) {
        cin >> K[i];
    }
    solve();
}