답안 #44268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44268	2018-03-31T05:55:29 Z	leejseo	Stove (JOI18_stove)	Python 2	20 / 100	1000 ms	60752 KB

stove

import sys
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 = [ [sys.maxint]*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.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	2936 KB	Output is correct
2	Correct	14 ms	3064 KB	Output is correct
3	Correct	13 ms	3064 KB	Output is correct
4	Correct	14 ms	3064 KB	Output is correct
5	Correct	14 ms	3064 KB	Output is correct
6	Correct	13 ms	3088 KB	Output is correct
7	Correct	13 ms	3104 KB	Output is correct
8	Correct	14 ms	3104 KB	Output is correct
9	Correct	13 ms	3112 KB	Output is correct

Subtask #2

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	2936 KB	Output is correct
2	Correct	14 ms	3064 KB	Output is correct
3	Correct	13 ms	3064 KB	Output is correct
4	Correct	14 ms	3064 KB	Output is correct
5	Correct	14 ms	3064 KB	Output is correct
6	Correct	13 ms	3088 KB	Output is correct
7	Correct	13 ms	3104 KB	Output is correct
8	Correct	14 ms	3104 KB	Output is correct
9	Correct	13 ms	3112 KB	Output is correct
10	Correct	39 ms	4492 KB	Output is correct
11	Correct	193 ms	12968 KB	Output is correct
12	Execution timed out	1067 ms	60752 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	2936 KB	Output is correct
2	Correct	14 ms	3064 KB	Output is correct
3	Correct	13 ms	3064 KB	Output is correct
4	Correct	14 ms	3064 KB	Output is correct
5	Correct	14 ms	3064 KB	Output is correct
6	Correct	13 ms	3088 KB	Output is correct
7	Correct	13 ms	3104 KB	Output is correct
8	Correct	14 ms	3104 KB	Output is correct
9	Correct	13 ms	3112 KB	Output is correct
10	Correct	39 ms	4492 KB	Output is correct
11	Correct	193 ms	12968 KB	Output is correct
12	Execution timed out	1067 ms	60752 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-