oj.uz

Submission #44269

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -