Submission #44267

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
44267	2018-03-31T05:54:33 Z	leejseo	Stove (JOI18_stove)	Python 2	20 / 100	1000 ms	65988 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) ]
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

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2936 KB	Output is correct
2	Correct	14 ms	3072 KB	Output is correct
3	Correct	13 ms	3072 KB	Output is correct
4	Correct	13 ms	3072 KB	Output is correct
5	Correct	17 ms	3072 KB	Output is correct
6	Correct	13 ms	3072 KB	Output is correct
7	Correct	13 ms	3180 KB	Output is correct
8	Correct	13 ms	3180 KB	Output is correct
9	Correct	13 ms	3180 KB	Output is correct

Subtask #2

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2936 KB	Output is correct
2	Correct	14 ms	3072 KB	Output is correct
3	Correct	13 ms	3072 KB	Output is correct
4	Correct	13 ms	3072 KB	Output is correct
5	Correct	17 ms	3072 KB	Output is correct
6	Correct	13 ms	3072 KB	Output is correct
7	Correct	13 ms	3180 KB	Output is correct
8	Correct	13 ms	3180 KB	Output is correct
9	Correct	13 ms	3180 KB	Output is correct
10	Correct	35 ms	4488 KB	Output is correct
11	Correct	205 ms	12960 KB	Output is correct
12	Execution timed out	1061 ms	65988 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2936 KB	Output is correct
2	Correct	14 ms	3072 KB	Output is correct
3	Correct	13 ms	3072 KB	Output is correct
4	Correct	13 ms	3072 KB	Output is correct
5	Correct	17 ms	3072 KB	Output is correct
6	Correct	13 ms	3072 KB	Output is correct
7	Correct	13 ms	3180 KB	Output is correct
8	Correct	13 ms	3180 KB	Output is correct
9	Correct	13 ms	3180 KB	Output is correct
10	Correct	35 ms	4488 KB	Output is correct
11	Correct	205 ms	12960 KB	Output is correct
12	Execution timed out	1061 ms	65988 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-