結果

問題 No.3760 Streaming Schedule
コンテスト
ユーザー titia
提出日時 2026-10-09 22:48:13
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 305 ms / 2,000 ms
+ 748µs
コード長 2,310 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 63 ms
コンパイル使用メモリ 81,652 KB
実行使用メモリ 165,188 KB
最終ジャッジ日時 2026-10-09 22:48:29
合計ジャッジ時間 6,513 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# https://atcoder.jp/contests/awc0042/submissions/78716921
# AWCで解けなかった問題。今も解法覚えてなかった……（セグ木でごちゃごちゃやることだけ覚えていた）

import sys
input = sys.stdin.readline

import sys
input = sys.stdin.readline

N,K,M=list(map(int,input().split()))
K,M=M,K
A=list(map(int,input().split()))
S=[0]
for a in A:
    S.append(S[-1]+a)

def seg_function(x,y): # Segment treeで扱うfunction
    return max(x,y)

seg_el=1<<((N+10).bit_length()) # Segment treeの台の要素数
SEG=[-1<<60]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def update(n,x,seg_el): # A[n]をxへ更新
    i=n+seg_el
    SEG[i]=x
    i>>=1 # 子ノードへ
    
    while i!=0:
        SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べる
    L=l+seg_el
    R=r+seg_el
    ANS1=-1<<60
    ANS2=-1<<60

    while L<R:
        if L & 1:
            ANS1=seg_function(ANS1, SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS2=seg_function(SEG[R], ANS2)
        L>>=1
        R>>=1

    return seg_function(ANS1, ANS2)

SEG2=[-1<<60]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def update2(n,x,seg_el): # A[n]をxへ更新
    i=n+seg_el
    SEG2[i]=x
    i>>=1 # 子ノードへ
    
    while i!=0:
        SEG2[i]=seg_function(SEG2[i*2],SEG2[i*2+1])
        i>>=1
        
def getvalues2(l,r): # 区間[l,r)に関するseg_functionを調べる
    L=l+seg_el
    R=r+seg_el
    ANS1=-1<<60
    ANS2=-1<<60

    while L<R:
        if L & 1:
            ANS1=seg_function(ANS1, SEG2[L])
            L+=1

        if R & 1:
            R-=1
            ANS2=seg_function(SEG2[R], ANS2)
        L>>=1
        R>>=1

    return seg_function(ANS1, ANS2)

for i in range(N):
    # i日目に仕事

    if i-K+1<0:
        update(i,S[i+1],seg_el)
    else:
        rest=getvalues2(i-K+1,i)
        #print(i,rest)
        update(i,rest+S[i+1],seg_el)

    # i日目に休み

    work=max(0,getvalues(max(0,i-M+1),i))
    update2(i,work-S[i+1],seg_el)

#print([getvalues(i,i+1) for i in range(N)])
#print([getvalues2(i,i+1) for i in range(N)])


ANS=getvalues(0,N)

print(ANS)
0