Submission #44272

#	Time	Username	Problem	Language	Result	Execution time	Memory
44272		leejseo	Stove (JOI18_stove)	Cpython 2	100 / 100	205 ms	19020 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())
''' O(NK) code
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])
'''
#### GREEDY APPROACH
#### If we turn-on stove k times,
#### Then, it is equivalent to turn-off stove on k-1 intervals
M = []
for i in range(N-1):
    M.append(T[i] - T[i+1])
M.sort()
ans = T[-1] - T[0] + K
for i in range(K-1):
    ans += M[i]
print ans

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