Submission #44266

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44266	2018-03-31T05:52:48 Z	leejseo	Stove (JOI18_stove)	Python 2	20 / 100	1000 ms	61204 KB

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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2936 KB	Output is correct
2	Correct	13 ms	2940 KB	Output is correct
3	Correct	14 ms	3036 KB	Output is correct
4	Correct	13 ms	3132 KB	Output is correct
5	Correct	13 ms	3228 KB	Output is correct
6	Correct	13 ms	3236 KB	Output is correct
7	Correct	14 ms	3252 KB	Output is correct
8	Correct	15 ms	3256 KB	Output is correct
9	Correct	18 ms	3260 KB	Output is correct

Subtask #2

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2936 KB	Output is correct
2	Correct	13 ms	2940 KB	Output is correct
3	Correct	14 ms	3036 KB	Output is correct
4	Correct	13 ms	3132 KB	Output is correct
5	Correct	13 ms	3228 KB	Output is correct
6	Correct	13 ms	3236 KB	Output is correct
7	Correct	14 ms	3252 KB	Output is correct
8	Correct	15 ms	3256 KB	Output is correct
9	Correct	18 ms	3260 KB	Output is correct
10	Correct	38 ms	4504 KB	Output is correct
11	Correct	209 ms	13112 KB	Output is correct
12	Execution timed out	1082 ms	61204 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2936 KB	Output is correct
2	Correct	13 ms	2940 KB	Output is correct
3	Correct	14 ms	3036 KB	Output is correct
4	Correct	13 ms	3132 KB	Output is correct
5	Correct	13 ms	3228 KB	Output is correct
6	Correct	13 ms	3236 KB	Output is correct
7	Correct	14 ms	3252 KB	Output is correct
8	Correct	15 ms	3256 KB	Output is correct
9	Correct	18 ms	3260 KB	Output is correct
10	Correct	38 ms	4504 KB	Output is correct
11	Correct	209 ms	13112 KB	Output is correct
12	Execution timed out	1082 ms	61204 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-