結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
52,608 KB
testcase_01 AC 42 ms
52,352 KB
testcase_02 AC 175 ms
75,520 KB
testcase_03 AC 267 ms
106,556 KB
testcase_04 AC 271 ms
106,296 KB
testcase_05 AC 271 ms
106,048 KB
testcase_06 AC 263 ms
106,172 KB
testcase_07 AC 271 ms
106,688 KB
testcase_08 AC 227 ms
106,176 KB
testcase_09 AC 232 ms
106,304 KB
testcase_10 AC 228 ms
105,920 KB
testcase_11 AC 246 ms
105,928 KB
testcase_12 AC 235 ms
106,044 KB
testcase_13 AC 58 ms
62,464 KB
testcase_14 AC 45 ms
59,648 KB
testcase_15 AC 57 ms
65,152 KB
testcase_16 AC 38 ms
51,968 KB
testcase_17 AC 36 ms
52,480 KB
testcase_18 AC 88 ms
77,048 KB
testcase_19 AC 91 ms
77,056 KB
testcase_20 AC 89 ms
76,724 KB
testcase_21 AC 43 ms
58,240 KB
testcase_22 AC 102 ms
76,912 KB
testcase_23 AC 136 ms
78,592 KB
testcase_24 AC 186 ms
85,888 KB
testcase_25 AC 222 ms
102,400 KB
testcase_26 AC 143 ms
78,208 KB
testcase_27 AC 166 ms
83,968 KB
testcase_28 AC 162 ms
84,352 KB
testcase_29 AC 143 ms
79,616 KB
testcase_30 AC 181 ms
88,064 KB
testcase_31 AC 249 ms
109,824 KB
testcase_32 AC 139 ms
80,896 KB
testcase_33 AC 227 ms
111,744 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