제출 #1345316

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1345316		hetingen69420	Feast (NOI19_feast)	Pypy 3	4 / 100	243 ms	207132 KiB

feast

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


def solve_lambda(penalty):
    dp_prev0 = 0
    count_prev0 = 0
    dp_prev1 = nums[0] - penalty
    count_prev1 = 1

    for i in range(1, N):
        (dp0, count0) = max(
            (dp_prev0, count_prev0),
            (dp_prev1, count_prev1),
        )

        (dp1, count1) = max(
            (dp_prev0 + nums[i] - penalty, count_prev0 + 1),
            (dp_prev1 + nums[i], count_prev1)
        )
        dp_prev0, dp_prev1 = dp0, dp1
        count_prev0, count_prev1 = count0, count1

    return max(
        (dp0, count0),
        (dp1, count1)
    )


lo = 0
hi = max(nums) + 1

while lo < hi - 1:
    mid = (lo + hi) // 2
    penalised, count = solve_lambda(mid)
    if count >= K:
        lo = mid
    else:
        hi = mid


penalised, count = solve_lambda(lo)
print(penalised + K * lo)

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'feast.py'...

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

=======

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