답안 #44270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44270	2018-03-31T05:56:45 Z	leejseo	Stove (JOI18_stove)	PyPy	50 / 100	1000 ms	262144 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	29 ms	11240 KB	Output is correct
2	Correct	28 ms	11364 KB	Output is correct
3	Correct	28 ms	11364 KB	Output is correct
4	Correct	30 ms	11364 KB	Output is correct
5	Correct	29 ms	11364 KB	Output is correct
6	Correct	30 ms	11404 KB	Output is correct
7	Correct	29 ms	11404 KB	Output is correct
8	Correct	30 ms	11468 KB	Output is correct
9	Correct	29 ms	11468 KB	Output is correct

Subtask #2

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	11240 KB	Output is correct
2	Correct	28 ms	11364 KB	Output is correct
3	Correct	28 ms	11364 KB	Output is correct
4	Correct	30 ms	11364 KB	Output is correct
5	Correct	29 ms	11364 KB	Output is correct
6	Correct	30 ms	11404 KB	Output is correct
7	Correct	29 ms	11404 KB	Output is correct
8	Correct	30 ms	11468 KB	Output is correct
9	Correct	29 ms	11468 KB	Output is correct
10	Correct	47 ms	15096 KB	Output is correct
11	Correct	63 ms	18140 KB	Output is correct
12	Correct	148 ms	38880 KB	Output is correct
13	Correct	212 ms	63432 KB	Output is correct
14	Correct	259 ms	85496 KB	Output is correct
15	Correct	300 ms	87828 KB	Output is correct

Subtask #3

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	11240 KB	Output is correct
2	Correct	28 ms	11364 KB	Output is correct
3	Correct	28 ms	11364 KB	Output is correct
4	Correct	30 ms	11364 KB	Output is correct
5	Correct	29 ms	11364 KB	Output is correct
6	Correct	30 ms	11404 KB	Output is correct
7	Correct	29 ms	11404 KB	Output is correct
8	Correct	30 ms	11468 KB	Output is correct
9	Correct	29 ms	11468 KB	Output is correct
10	Correct	47 ms	15096 KB	Output is correct
11	Correct	63 ms	18140 KB	Output is correct
12	Correct	148 ms	38880 KB	Output is correct
13	Correct	212 ms	63432 KB	Output is correct
14	Correct	259 ms	85496 KB	Output is correct
15	Correct	300 ms	87828 KB	Output is correct
16	Correct	116 ms	87828 KB	Output is correct
17	Correct	479 ms	109700 KB	Output is correct
18	Execution timed out	1074 ms	262144 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-