Submission #13992877


Source Code Expand

Copy
N, K = map(int, input().split())
b = [int(input()) for i in range(N)]
sums = [0 for i in range(N)]
sums[0] = b[0]
for i in range(1, N):
    sums[i] = sums[i-1]+b[i]
dp = [-10**20 for i in range(N+1)]  # dp[i]左からi番目を右端としてそこまでに対してK選択を行った時の最大値
X = dp.copy()
for i in range(1, K):
    dp[i] = sums[i-1]
    X[i] = dp[i]
    dp[i] = max(dp[i-1], dp[i])
dp[0] = 0
X[0] = 0
for i in range(K, N+1):
    dp[i] = max(X[i-1]+b[i-1], dp[i-K])
    X[i] = dp[i]
    dp[i] = max(dp[i-1], dp[i])
ans = max(sum(b), X[N])

print(ans)

Submission Info

Submission Time
Task B - Neutralize
User kurimu_usamaro
Language Python3 (3.4.3)
Score 0
Code Size 595 Byte
Status
Exec Time 624 ms
Memory 29748 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03, a04
All 0 / 400 a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44
Case Name Status Exec Time Memory
a01 17 ms 3064 KB
a02 17 ms 3064 KB
a03 17 ms 3064 KB
a04 17 ms 3064 KB
b05 17 ms 3064 KB
b06 17 ms 3064 KB
b07 67 ms 5208 KB
b08 510 ms 23592 KB
b09 585 ms 22852 KB
b10 514 ms 18876 KB
b11 514 ms 18876 KB
b12 17 ms 3064 KB
b13 553 ms 23200 KB
b14 558 ms 23204 KB
b15 569 ms 24728 KB
b16 590 ms 24032 KB
b17 569 ms 23812 KB
b18 569 ms 23700 KB
b19 565 ms 23708 KB
b20 542 ms 23740 KB
b21 546 ms 22636 KB
b22 542 ms 25872 KB
b23 581 ms 23596 KB
b24 458 ms 22944 KB
b25 585 ms 23468 KB
b26 557 ms 23436 KB
b27 542 ms 22468 KB
b28 589 ms 25772 KB
b29 554 ms 22160 KB
b30 321 ms 16280 KB
b31 562 ms 26160 KB
b32 557 ms 23504 KB
b33 468 ms 20536 KB
b34 558 ms 23764 KB
b35 529 ms 25112 KB
b36 619 ms 29352 KB
b37 615 ms 29724 KB
b38 595 ms 29648 KB
b39 594 ms 27248 KB
b40 578 ms 29588 KB
b41 580 ms 27860 KB
b42 624 ms 29748 KB
b43 559 ms 28360 KB
b44 586 ms 27944 KB