Submission #44270

#	Time	Username	Problem	Language	Result	Execution time	Memory
44270		leejseo	Stove (JOI18_stove)	Pypy 2	50 / 100	1074 ms	262144 KiB

stove

import sys
c = int(2E9)
raw_input = sys.stdin.readline
range = xrange
N, K = map(int, raw_input().split())
T = [0 for i in range(N) ]
for i in range(N):
    T[i] = int(raw_input())
DP = [ [c]*K for i in xrange(N) ]
DIFF = [0]*N
for i in range(1, N):
    DIFF[i] = T[i] - T[i-1]
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] + DIFF[i],
                       DP[i-1][j-1] + 1)
print min(DP[N-1])

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