Submission #13993234


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 = [-10**20 for i in range(N+1)]
dp[0] = 0
X[0] = 0
for i in range(1, K):
    dp[i] = sums[i-1]
    X[i] = dp[i]
    dp[i] = max(dp[i-1], dp[i])

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 PyPy3 (2.4.0)
Score 400
Code Size 617 Byte
Status
Exec Time 867 ms
Memory 75768 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03, a04
All 400 / 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 163 ms 38256 KB
a02 164 ms 38256 KB
a03 163 ms 38256 KB
a04 161 ms 38256 KB
b05 160 ms 38256 KB
b06 162 ms 38256 KB
b07 293 ms 45912 KB
b08 803 ms 75644 KB
b09 821 ms 75636 KB
b10 787 ms 75640 KB
b11 800 ms 75716 KB
b12 162 ms 38256 KB
b13 777 ms 75388 KB
b14 836 ms 75388 KB
b15 812 ms 75640 KB
b16 802 ms 75640 KB
b17 838 ms 75640 KB
b18 789 ms 75640 KB
b19 825 ms 75644 KB
b20 746 ms 71888 KB
b21 807 ms 75384 KB
b22 786 ms 75768 KB
b23 812 ms 75644 KB
b24 661 ms 68316 KB
b25 809 ms 75640 KB
b26 813 ms 75644 KB
b27 772 ms 75384 KB
b28 798 ms 75388 KB
b29 817 ms 75384 KB
b30 537 ms 61016 KB
b31 827 ms 75644 KB
b32 782 ms 75384 KB
b33 688 ms 68444 KB
b34 786 ms 72016 KB
b35 803 ms 75768 KB
b36 839 ms 75704 KB
b37 867 ms 75640 KB
b38 808 ms 75640 KB
b39 811 ms 75768 KB
b40 806 ms 75640 KB
b41 800 ms 75640 KB
b42 824 ms 75640 KB
b43 802 ms 75636 KB
b44 831 ms 75636 KB