Submission #1344747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344747		hetingen69420	Feast (NOI19_feast)	Pypy 3	41 / 100	261 ms	327680 KiB

feast

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


def solve_lambda(penalty):
    dp = [[0, 0] for _ in range(N)]
    count = [[0, 0] for _ in range(N)]

    dp[0][1] = nums[0] - penalty
    count[0][1] = 1

    for i in range(1, N):
        (dp[i][0], count[i][0]) = max(
            (dp[i - 1][0], count[i - 1][0]),
            (dp[i - 1][1], count[i - 1][1]),
        )

        (dp[i][1], count[i][1]) = max(
            (dp[i - 1][0] + nums[i] - penalty, count[i - 1][0] + 1),
            (dp[i - 1][1] + nums[i], count[i - 1][1])
        )

    return max(
        (dp[N - 1][0], count[N - 1][0]),
        (dp[N - 1][1], count[N - 1][1])
    )


lo = 0
hi = sum(map(abs, nums)) + 1

for _ in range(60):
    mid = (lo + hi) / 2
    penalised, count = solve_lambda(mid)
    if count >= K:
        lo = mid
    else:
        hi = mid


penalised, count = solve_lambda(hi)
print(int(round(penalised + K * hi)))

Compilation message (stdout)

Compiling 'feast.py'...

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

=======

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