Submission #13993224


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()
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 0
Code Size 597 Byte
Status
Exec Time 844 ms
Memory 74168 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 164 ms 38256 KB
a02 177 ms 38256 KB
a03 178 ms 38256 KB
a04 179 ms 38256 KB
b05 166 ms 38256 KB
b06 167 ms 38256 KB
b07 290 ms 44504 KB
b08 818 ms 73764 KB
b09 812 ms 73764 KB
b10 794 ms 73764 KB
b11 832 ms 73764 KB
b12 174 ms 38256 KB
b13 779 ms 73508 KB
b14 820 ms 73508 KB
b15 804 ms 73764 KB
b16 785 ms 73764 KB
b17 789 ms 73764 KB
b18 808 ms 73764 KB
b19 826 ms 74168 KB
b20 731 ms 70224 KB
b21 762 ms 73508 KB
b22 795 ms 73764 KB
b23 790 ms 73764 KB
b24 662 ms 66780 KB
b25 793 ms 73764 KB
b26 822 ms 73764 KB
b27 761 ms 73840 KB
b28 792 ms 73380 KB
b29 769 ms 73508 KB
b30 516 ms 59224 KB
b31 767 ms 73764 KB
b32 752 ms 73508 KB
b33 661 ms 66780 KB
b34 723 ms 70224 KB
b35 783 ms 73764 KB
b36 844 ms 73764 KB
b37 798 ms 73764 KB
b38 763 ms 73764 KB
b39 817 ms 73764 KB
b40 777 ms 73764 KB
b41 797 ms 73764 KB
b42 836 ms 73764 KB
b43 810 ms 73764 KB
b44 790 ms 73764 KB