연세워터파크

• 문제 조건은 왼쪽과 오른쪽으로 점프가 가능하지만, 한쪽 방향으로만 점프해서 이동해도 최적값을 찾을수 있다는 것은 쉽게 떠올릴수 있다.
• 그러면 왼쪽에서 오른쪽으로만 이동한다고 가정하고 최대값을 dp로 계산하자.
• dp[i]를 i번째 징검다리에 도착했을때 가질수 있는 최대 점수라고 하면, dp[i] = K[i] + max(0, dp[i-1], dp[i-2], .. ,dp[i-D+1]) 로 점화식이 나온다.
• 이 점화식을 그냥 풀면 O(nd)이지만, monotone deque 테크닉을 활용해서 O(n)에 풀수 있다.

"""Solution code for "BOJ 15678. 연세워터파크".

- Problem link: https://www.acmicpc.net/problem/15678
- Solution link: http://www.teferi.net/ps/problems/boj/15678

Tags: [DP] [Monotone queue]
"""

import collections

INF = float('inf')


def main():
    N, D = [int(x) for x in input().split()]
    K = [int(x) for x in input().split()]

    deq = collections.deque([-INF])
    dp = [-INF] * D
    for dp_left, k_i in zip(dp, K):
        dp_cur = k_i + max(0, deq[0])
        while deq and deq[-1] < dp_cur:
            deq.pop()
        deq.append(dp_cur)
        dp.append(dp_cur)
        if deq[0] == dp_left:
            deq.popleft()

    print(max(dp))


if __name__ == '__main__':
    main()