Submission #44266

#	Time	Username	Problem	Language	Result	Execution time	Memory
44266		leejseo	Stove (JOI18_stove)	Cpython 2	20 / 100	1082 ms	61204 KiB

stove

import sys
raw_input = sys.stdin.readline
range = xrange
N, K = map(int, raw_input().split())
T = [None]*N
for i in range(N):
    T[i] = int(raw_input())
DP = [ [sys.maxint]*K for i in xrange(N) ]

for i in range(K):
    DP[0][i] = 1
for i in range(1, N):
    DP[i][0] = T[i] + 1 - T[0]
    for j in range(1, K):
        DP[i][j] = min(DP[i-1][j] + T[i] - T[i-1],
                       DP[i-1][j-1] + 1)
print min(DP[N-1])

• Subtask 1: 20 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50