답안 #44267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-