Submission #1311605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311605		mtandon	Feast (NOI19_feast)	Pypy 3	100 / 100	363 ms	106240 KiB

feast

import sys

input = sys.stdin.readline

n, k = map(int, input().split())

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


def opt(l):
    dp = [tuple()]*2 # old tuple, new tuple, storing max value, number arrays
    dp[0] = (0, 0)
    dp[1] = (A[0] - l, -1)

    for i in range(1, n):
        tmp0 = max(dp[0], dp[1])
        tmp1 = max(
            (dp[0][0] - l + A[i], dp[0][1] - 1), 
            (dp[1][0] + A[i], dp[1][1])
            )
        
        dp[0] = tmp0
        dp[1] = tmp1

    return max(dp)

lo = 0
hi = int(3e14)

while lo < hi:
    mid = (lo+hi)//2

    res = opt(mid)
    ktemp = -res[1]

    if ktemp > k:
        lo = mid + 1
    else:
        hi = mid
        
res = opt(lo)
print(res[0] + k*lo)

Compilation message (stdout)

Compiling 'feast.py'...

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

=======

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