제출 #1311587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311587		eyangch	Feast (NOI19_feast)	Pypy 3	100 / 100	361 ms	106340 KiB

feast

import sys

input = sys.stdin.readline

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

def solve_opt(l):
    dp = [tuple()] * 2  # (score, -num_subarr)
    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[1][0] + A[i], dp[1][1]),
            (dp[0][0] + A[i] - l, dp[0][1] - 1)
        )
        dp[0] = tmp0
        dp[1] = tmp1
    # end up with max score, with min number of subarrays used for that score
    return max(dp)

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

# lo is now optimal lambda
print(solve_opt(lo)[0] + K * lo)    

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

Compiling 'feast.py'...

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

=======

• 서브태스크 1: 4 / 4
• 서브태스크 2: 8 / 8
• 서브태스크 3: 18 / 18
• 서브태스크 4: 10 / 10
• 서브태스크 5: 11 / 11
• 서브태스크 6: 20 / 20
• 서브태스크 7: 29 / 29