結果

問題 No.2139 K Consecutive Sushi
ユーザー ShirotsumeShirotsume
提出日時 2022-09-30 03:03:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 298 ms / 2,000 ms
コード長 2,483 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 82,128 KB
実行使用メモリ 111,872 KB
最終ジャッジ日時 2024-11-27 19:45:57
合計ジャッジ時間 7,204 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,608 KB
testcase_01 AC 37 ms
52,352 KB
testcase_02 AC 184 ms
75,648 KB
testcase_03 AC 298 ms
106,532 KB
testcase_04 AC 290 ms
106,048 KB
testcase_05 AC 284 ms
106,308 KB
testcase_06 AC 282 ms
106,428 KB
testcase_07 AC 293 ms
105,928 KB
testcase_08 AC 245 ms
105,976 KB
testcase_09 AC 247 ms
105,664 KB
testcase_10 AC 253 ms
106,400 KB
testcase_11 AC 255 ms
105,656 KB
testcase_12 AC 254 ms
106,304 KB
testcase_13 AC 50 ms
62,848 KB
testcase_14 AC 44 ms
59,008 KB
testcase_15 AC 53 ms
65,536 KB
testcase_16 AC 39 ms
52,480 KB
testcase_17 AC 39 ms
51,968 KB
testcase_18 AC 89 ms
76,544 KB
testcase_19 AC 90 ms
76,416 KB
testcase_20 AC 89 ms
76,792 KB
testcase_21 AC 43 ms
58,496 KB
testcase_22 AC 103 ms
76,524 KB
testcase_23 AC 146 ms
78,848 KB
testcase_24 AC 178 ms
85,248 KB
testcase_25 AC 231 ms
102,272 KB
testcase_26 AC 140 ms
78,080 KB
testcase_27 AC 170 ms
84,608 KB
testcase_28 AC 170 ms
84,352 KB
testcase_29 AC 153 ms
79,872 KB
testcase_30 AC 186 ms
88,192 KB
testcase_31 AC 273 ms
109,184 KB
testcase_32 AC 152 ms
80,896 KB
testcase_33 AC 243 ms
111,872 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