Submission #44270

# Submission time Handle Problem Language Result Execution time Memory
44270 2018-03-31T05:56:45 Z leejseo Stove (JOI18_stove) PyPy
50 / 100
1000 ms 262144 KB
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])
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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 -