Submission #12447851


Source Code Expand

Copy
"""
Writer: SPD_9X2
https://atcoder.jp/contests/soundhound2018-summer-final/tasks/soundhound2018_summer_final_b

dp[i] = i番目の薬品まで見た時に達成できる最大値?

dp[i] = dp[i-1] + b[i] →採用した場合
dp[i] = max(dp[0],dp[1]…dp[i-k]) →採用しない場合

で求められる?

"""

N,K = map(int,input().split())

mlis = [0]

dp = [0]

for i in range(N):

    b = int(input())

    now = dp[-1] + b

    if i+1-K >= 0:
        now = max(now , mlis[i+1-K])

    dp.append(now)
    mlis.append(max(mlis[-1] , now))

#print (dp)
print (dp[-1])

Submission Info

Submission Time
Task B - Neutralize
User SPD_9X2
Language PyPy3 (2.4.0)
Score 400
Code Size 612 Byte
Status
Exec Time 854 ms
Memory 73304 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 161 ms 38256 KB
a02 160 ms 38256 KB
a03 160 ms 38256 KB
a04 162 ms 38256 KB
b05 161 ms 38256 KB
b06 160 ms 38256 KB
b07 277 ms 43992 KB
b08 759 ms 71256 KB
b09 784 ms 71768 KB
b10 786 ms 71256 KB
b11 794 ms 71384 KB
b12 160 ms 38256 KB
b13 738 ms 72024 KB
b14 767 ms 72024 KB
b15 811 ms 72792 KB
b16 854 ms 72536 KB
b17 813 ms 72536 KB
b18 810 ms 72408 KB
b19 827 ms 72408 KB
b20 746 ms 68952 KB
b21 772 ms 72408 KB
b22 781 ms 72408 KB
b23 824 ms 72664 KB
b24 700 ms 65624 KB
b25 766 ms 72792 KB
b26 818 ms 72536 KB
b27 752 ms 72408 KB
b28 773 ms 72280 KB
b29 771 ms 72792 KB
b30 533 ms 58328 KB
b31 793 ms 72920 KB
b32 761 ms 72152 KB
b33 668 ms 65880 KB
b34 743 ms 68824 KB
b35 793 ms 73304 KB
b36 824 ms 73176 KB
b37 802 ms 72920 KB
b38 770 ms 72280 KB
b39 795 ms 72408 KB
b40 786 ms 72920 KB
b41 797 ms 72664 KB
b42 811 ms 72728 KB
b43 835 ms 72664 KB
b44 798 ms 72664 KB