답안 #44269

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	2884 KB	Output is correct
2	Correct	13 ms	3000 KB	Output is correct
3	Correct	17 ms	3024 KB	Output is correct
4	Correct	13 ms	3024 KB	Output is correct
5	Correct	14 ms	3024 KB	Output is correct
6	Correct	13 ms	3040 KB	Output is correct
7	Correct	15 ms	3040 KB	Output is correct
8	Correct	14 ms	3040 KB	Output is correct
9	Correct	14 ms	3044 KB	Output is correct

Subtask #2

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	2884 KB	Output is correct
2	Correct	13 ms	3000 KB	Output is correct
3	Correct	17 ms	3024 KB	Output is correct
4	Correct	13 ms	3024 KB	Output is correct
5	Correct	14 ms	3024 KB	Output is correct
6	Correct	13 ms	3040 KB	Output is correct
7	Correct	15 ms	3040 KB	Output is correct
8	Correct	14 ms	3040 KB	Output is correct
9	Correct	14 ms	3044 KB	Output is correct
10	Correct	64 ms	4408 KB	Output is correct
11	Correct	273 ms	12936 KB	Output is correct
12	Execution timed out	1067 ms	63348 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	2884 KB	Output is correct
2	Correct	13 ms	3000 KB	Output is correct
3	Correct	17 ms	3024 KB	Output is correct
4	Correct	13 ms	3024 KB	Output is correct
5	Correct	14 ms	3024 KB	Output is correct
6	Correct	13 ms	3040 KB	Output is correct
7	Correct	15 ms	3040 KB	Output is correct
8	Correct	14 ms	3040 KB	Output is correct
9	Correct	14 ms	3044 KB	Output is correct
10	Correct	64 ms	4408 KB	Output is correct
11	Correct	273 ms	12936 KB	Output is correct
12	Execution timed out	1067 ms	63348 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-