#799604 (Python3) No.2028 Even Choice

提出ソース

結果

問題	No.2028 Even Choice
ユーザー	vwxyz
提出日時	2022-09-22 05:05:18
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	628 ms / 2,000 ms
コード長	5,893 bytes
コンパイル時間	88 ms
コンパイル使用メモリ	13,184 KB
実行使用メモリ	34,628 KB
最終ジャッジ日時	2024-06-01 17:46:25
合計ジャッジ時間	7,662 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	600 ms 34,224 KB
testcase_01	AC	508 ms 34,092 KB
testcase_02	AC	628 ms 34,096 KB
testcase_03	AC	351 ms 34,504 KB
testcase_04	AC	364 ms 34,628 KB
testcase_05	AC	138 ms 17,056 KB
testcase_06	AC	554 ms 31,988 KB
testcase_07	AC	154 ms 18,104 KB
testcase_08	AC	374 ms 25,632 KB
testcase_09	AC	388 ms 28,016 KB
testcase_10	AC	125 ms 18,104 KB
testcase_11	AC	131 ms 15,996 KB
testcase_12	AC	77 ms 13,824 KB
testcase_13	AC	302 ms 29,416 KB
testcase_14	AC	183 ms 18,228 KB
testcase_15	AC	42 ms 12,288 KB
testcase_16	AC	42 ms 12,288 KB
testcase_17	AC	42 ms 12,288 KB
testcase_18	AC	47 ms 12,160 KB
testcase_19	AC	45 ms 12,288 KB
testcase_20	AC	43 ms 12,416 KB
testcase_21	AC	45 ms 12,416 KB
testcase_22	AC	45 ms 12,288 KB
testcase_23	AC	43 ms 12,416 KB
testcase_24	AC	42 ms 12,288 KB
testcase_25	AC	44 ms 12,288 KB
testcase_26	AC	42 ms 12,288 KB
testcase_27	AC	45 ms 12,288 KB
testcase_28	AC	157 ms 26,428 KB
testcase_29	AC	122 ms 21,348 KB
testcase_30	AC	98 ms 18,508 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
write=sys.stdout.write

class Slope_Trick:
    def __init__(self,L=False,R=False,median=False,label=False,f=None,f_inve=None,e=None):
        self.queueL=[]
        self.queueR=[]
        self.L=L
        self.R=R
        self.median=median
        if self.median:
            self.median_value=None
        self.label=label
        if self.label:
            self.f=f
            self.f_inve=f_inve
            self.e=e
            self.labelL=self.e
            self.labelR=self.e

    def heappush(self,x):
        heappush(self.queueR,x)
        if self.label:
            self.labelR=self.f(self.labelR,x)

    def heappop(self):
        x=heappop(self.queueR)
        if self.label:
            self.labelR=self.f_inve(self.labelR,x)
        return x

    def heappushpop(self,x):
        y=heappushpop(self.queueR,x)
        if self.label:
            self.labelR=self.f(self.labelR,x)
            self.labelR=self.f_inve(self.labelR,y)
        return y

    def _heappush_max(self,x):
        _heappush_max(self.queueL,x)
        if self.label:
            self.labelL=self.f(self.labelL,x)

    def _heappop_max(self):
        x=_heappop_max(self.queueL)
        if self.label:
            self.labelL=self.f_inve(self.labelL,x)
        return x

    def _heappushpop_max(self,x):
        y=_heappushpop_max(self.queueL,x)
        if self.label:
            self.labelL=self.f(self.labelL,x)
            self.labelL=self.f_inve(self.labelL,y)
        return y

    def push_Left(self,x):
        self._heappush_max(self.heappushpop(x))

    def push_Right(self,x):
        self.heappush(self._heappushpop_max(x))

    def pop_Left(self):
        if self.queueL:
            retu=self._heappop_max()
        else:
            retu=None
        return retu

    def pop_Right(self):
        if self.queueR:
            retu=self.heappop()
        else:
            retu=None
        return retu

    def push(self,x):
        if self.L:
            if len(self.queueL)<self.L:
                self.push_Left(x)
            else:
                self.push_Right(x)
        if self.R:
            if len(self.queueR)<self.R:
                self.push_Right(x)
            else:
                self.push_Left(x)
        if self.median:
            if self.median_value==None:
                if self.queueL and x<self.queueL[0]:
                    self.median_value=self._heappushpop_max(x)
                elif self.queueR and self.queueR[0]<x:
                    self.median_value=self.heappushpop(x)
                else:
                    self.median_value=x
            else:
                if self.median_value<=x:
                    self._heappush_max(self.median_value)
                    self.heappush(x)
                else:
                    self._heappush_max(x)
                    self.heappush(self.median_value)
                self.median_value=None

    def pop(self):
        if self.L:
            if len(self.queueL)==self.L:
                retu=self._heappop_max()
                if self.queueR:
                    self._heappush_max(self.heappop())
            else:
                retu=None
        if self.R:
            if len(self.queueR)==self.R:
                retu=self.heappop()
                if self.queueL:
                    self.heappush(self._heappop_max())
            else:
                retu=None
        if self.median:
            if self.median_value==None:
                retu=(self.Pop_Left(),self.Pop_Right())
            else:
                retu=(self.median_value,None)
                self.median_value=None
        return retu

    def top(self):
        if self.L:
            if len(self.queueL)==self.L:
                retu=self.queueL[0]
            else:
                retu=None
        if self.R:
            if len(self.queueR)==self.R:
                retu=self.queueR[0]
            else:
                retu=None
        if self.median:
            if self.median_value==None:
                if self.queueL:
                    retu=(self.queueL[0],self.queueR[0])
                else:
                    retu=(None,None)
            else:
                retu=(self.median_value,None)
        return retu

    def Label_Left(self):
        return self.labelL

    def Label_Right(self):
        return self.labelR

    def __len__(self):
        retu=len(self.queueL)+len(self.queueR)
        if self.median and self.median_value!=None:
            retu+=1
        return retu

    def __str__(self):
        if self.median:
            if self.median_value==None:
                return "["+", ".join(map(str,sorted(self.queueL)))+"]+["+", ".join(map(str,sorted(self.queueR)))+"]"
            else:
                return "["+", ".join(map(str,sorted(self.queueL)))+"]+"+str(self.median_value)+"+["+", ".join(map(str,sorted(self.queueR)))+"]"
        else:
            return "["+", ".join(map(str,sorted(self.queueL)))+"]+["+", ".join(map(str,sorted(self.queueR)))+"]"

N,K=map(int,readline().split())
A=list(map(int,readline().split()))
ST=Slope_Trick(R=K-1,label=True,f=lambda x,y:x+y,f_inve=lambda x,y:x-y,e=0)
ans=0
for i in range(N-1,-1,-1):
    if i%2:
        ans=max(ans,ST.Label_Right()+A[i])
    ST.push(A[i])
print(ans)

yukicoder

結果

テストケース

ソースコード