結果

問題 No.2139 K Consecutive Sushi
ユーザー ShirotsumeShirotsume
提出日時 2022-09-30 03:03:35
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 318 ms / 2,000 ms
コード長 2,483 bytes
コンパイル時間 483 ms
コンパイル使用メモリ 87,292 KB
実行使用メモリ 107,728 KB
最終ジャッジ日時 2023-07-31 08:16:20
合計ジャッジ時間 8,609 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
71,360 KB
testcase_01 AC 70 ms
71,484 KB
testcase_02 AC 210 ms
77,496 KB
testcase_03 AC 317 ms
107,616 KB
testcase_04 AC 314 ms
107,532 KB
testcase_05 AC 308 ms
107,472 KB
testcase_06 AC 304 ms
107,444 KB
testcase_07 AC 318 ms
107,728 KB
testcase_08 AC 275 ms
107,156 KB
testcase_09 AC 271 ms
107,320 KB
testcase_10 AC 282 ms
107,188 KB
testcase_11 AC 279 ms
107,228 KB
testcase_12 AC 275 ms
107,468 KB
testcase_13 AC 82 ms
76,240 KB
testcase_14 AC 75 ms
76,224 KB
testcase_15 AC 83 ms
76,824 KB
testcase_16 AC 70 ms
71,632 KB
testcase_17 AC 72 ms
71,432 KB
testcase_18 AC 117 ms
77,884 KB
testcase_19 AC 117 ms
78,168 KB
testcase_20 AC 114 ms
78,008 KB
testcase_21 AC 77 ms
75,152 KB
testcase_22 AC 132 ms
78,856 KB
testcase_23 AC 171 ms
79,676 KB
testcase_24 AC 213 ms
87,268 KB
testcase_25 AC 262 ms
103,760 KB
testcase_26 AC 172 ms
79,732 KB
testcase_27 AC 198 ms
85,980 KB
testcase_28 AC 197 ms
85,804 KB
testcase_29 AC 179 ms
81,160 KB
testcase_30 AC 209 ms
89,460 KB
testcase_31 AC 300 ms
104,328 KB
testcase_32 AC 176 ms
81,576 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
mod = 998244353
class segtree():
    n=1
    size=1
    log=2
    d=[0]
    op=None
    e=10**15
    def __init__(self,V,OP,E):
        self.n=len(V)
        self.op=OP
        self.e=E
        self.log=(self.n-1).bit_length()
        self.size=1<<self.log
        self.d=[E for i in range(2*self.size)]
        for i in range(self.n):
            self.d[self.size+i]=V[i]
        for i in range(self.size-1,0,-1):
            self.update(i)
    def set(self,p,x):
        assert 0<=p and p<self.n
        p+=self.size
        self.d[p]=x
        for i in range(1,self.log+1):
            self.update(p>>i)
    def get(self,p):
        assert 0<=p and p<self.n
        return self.d[p+self.size]
 
    def __setitem__(self, p, x):
        self.set(p, x)
    
    def __getitem__(self, p):
        if isinstance(p, int):
            return self.get(p)
        else:
            return self.prod(p.start, p.stop)
 
    def prod(self,l,r):
        assert 0<=l and l<=r and r<=self.n
        sml=self.e
        smr=self.e
        l+=self.size
        r+=self.size
        while(l<r):
            if (l&1):
                sml=self.op(sml,self.d[l])
                l+=1
            if (r&1):
                smr=self.op(self.d[r-1],smr)
                r-=1
            l>>=1
            r>>=1
        return self.op(sml,smr)
    
    def all_prod(self):
        return self.d[1]
 
    def update(self,k):
        self.d[k]=self.op(self.d[2*k],self.d[2*k+1])
 
    def __str__(self):
        return str([self.get(i) for i in range(self.n)])

def solve_gu(n, k, a):
    ans = 0
    for bit in range(1<<n):
        ch = [0] * n
        for i in range(n):
            if 1 & (bit >> i):
                ch[i] = a[i]
        now = sum(ch)
        for i in range(n - k + 1):
            fl = True
            for j in range(k):
                if ch[i + j] == 0:
                    fl = False
            if fl:
                now = 0
        if now > 0:
            ans = max(ans, now)
    return ans


def solve(n, k, a):
    if n <= 20:
        return solve_gu(n, k, a)
    inf = 10 ** 18
    dp = segtree([inf] * (n + 2), min, inf)
    dp[0] = 0
    a.append(0)
    for i in range(1, n + 2):
        dp[i] = dp[max(0, i - k):i] + a[i-1]
    a.pop()
    return sum(a) - dp[n+1]

n, k = mi()

a = li()

print(solve(n, k, a))
0