Submission #1311207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311207		eyangch	Feast (NOI19_feast)	Pypy 3	12 / 100	916 ms	285772 KiB

feast

import sys

input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))

dp = [[0] * 2 for _ in range(N)]

def solve_opt(lambd):
    dp[0][0] = (0, 0)
    dp[0][1] = (A[0] - lambd, -1)
    for i in range(1, N):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        opt1 = (dp[i-1][0][0] - lambd, dp[i-1][0][1] - 1)
        opt = max(opt1, dp[i-1][1])
        dp[i][1] = (opt[0] + A[i], opt[1])
    return max(dp[N-1][0], dp[N-1][1])

lo = 0
hi = int(3e14)
while lo < hi:
    mid = (lo + hi) // 2
    res = solve_opt(mid)
    used = -res[1]
    if used > K:
        lo = mid+1
    else:
        hi = mid

res = solve_opt(lo)
print(res[0] + K * lo)

Compilation message (stdout)

Compiling 'feast.py'...

=======
  adding: __main__.pyc (deflated 38%)

=======

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29