結果

問題 No.2139 K Consecutive Sushi
ユーザー Shirotsume
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

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