結果

問題 No.2028 Even Choice
ユーザー siganaisiganai
提出日時 2022-08-05 21:52:41
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,757 bytes
コンパイル時間 489 ms
コンパイル使用メモリ 87,164 KB
実行使用メモリ 118,412 KB
最終ジャッジ日時 2023-10-13 22:36:06
合計ジャッジ時間 10,178 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 494 ms
114,228 KB
testcase_01 AC 510 ms
118,412 KB
testcase_02 AC 460 ms
113,984 KB
testcase_03 AC 286 ms
114,712 KB
testcase_04 AC 288 ms
114,608 KB
testcase_05 AC 302 ms
90,492 KB
testcase_06 AC 446 ms
110,524 KB
testcase_07 AC 317 ms
92,740 KB
testcase_08 AC 349 ms
102,044 KB
testcase_09 AC 425 ms
104,520 KB
testcase_10 AC 263 ms
92,192 KB
testcase_11 AC 295 ms
88,560 KB
testcase_12 AC 250 ms
86,080 KB
testcase_13 AC 409 ms
107,168 KB
testcase_14 AC 302 ms
93,724 KB
testcase_15 AC 152 ms
80,612 KB
testcase_16 AC 153 ms
80,500 KB
testcase_17 AC 154 ms
80,668 KB
testcase_18 AC 155 ms
80,564 KB
testcase_19 AC 157 ms
80,580 KB
testcase_20 AC 163 ms
82,128 KB
testcase_21 AC 168 ms
82,096 KB
testcase_22 AC 163 ms
82,036 KB
testcase_23 RE -
testcase_24 AC 153 ms
80,496 KB
testcase_25 RE -
testcase_26 AC 154 ms
80,304 KB
testcase_27 AC 159 ms
80,464 KB
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
import functools
import heapq
import itertools
import math
import operator
import re
import sys
import typing
from collections import Counter, defaultdict, deque
from functools import reduce
import sys

input=sys.stdin.readline

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
su = 0
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')
class SortedMultiset(Generic[T]):
    BUCKET_RATIO = 50
    REBUILD_RATIO = 170

    def _build(self, a=None) -> None:
        "Evenly divide `a` into buckets."
        if a is None: a = list(self)
        size = self.size = len(a)
        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
        self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]
    
    def __init__(self, a: Iterable[T] = []) -> None:
        "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
        a = list(a)
        if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
            a = sorted(a)
        self._build(a)

    def __iter__(self) -> Iterator[T]:
        for i in self.a:
            for j in i: yield j

    def __reversed__(self) -> Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i): yield j
    
    def __len__(self) -> int:
        return self.size
    
    def __repr__(self) -> str:
        return "SortedMultiset" + str(self.a)
    
    def __str__(self) -> str:
        s = str(list(self))
        return "{" + s[1 : len(s) - 1] + "}"

    def _find_bucket(self, x: T) -> List[T]:
        "Find the bucket which should contain x. self must not be empty."
        for a in self.a:
            if x <= a[-1]: return a
        return a

    def __contains__(self, x: T) -> bool:
        if self.size == 0: return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        return i != len(a) and a[i] == x

    def count(self, x: T) -> int:
        "Count the number of x."
        return self.index_right(x) - self.index(x)

    def add(self, x: T) -> None:
        "Add an element. / O(√N)"
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return
        a = self._find_bucket(x)
        insort(a, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()

    def discard(self, x: T) -> bool:
        "Remove an element and return True if removed. / O(√N)"
        if self.size == 0: return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i == len(a) or a[i] != x: return False
        a.pop(i)
        self.size -= 1
        if len(a) == 0: self._build()
        return True

    def lt(self, x: T) -> Union[T, None]:
        "Find the largest element < x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]

    def le(self, x: T) -> Union[T, None]:
        "Find the largest element <= x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]

    def gt(self, x: T) -> Union[T, None]:
        "Find the smallest element > x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]

    def ge(self, x: T) -> Union[T, None]:
        "Find the smallest element >= x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]
    
    def __getitem__(self, x: int) -> T:
        "Return the x-th element, or IndexError if it doesn't exist."
        if x < 0: x += self.size
        if x < 0: raise IndexError
        for a in self.a:
            if x < len(a): return a[x]
            x -= len(a)
        raise IndexError

    def index(self, x: T) -> int:
        "Count the number of elements < x."
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans

    def index_right(self, x: T) -> int:
        "Count the number of elements <= x."
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans
ms = SortedMultiset()
cnt = 0
for i in range(1,n)[::-1]:
    if i % 2:
        ans = max(ans,su + a[i])
    if cnt < k - 1:
        su += a[i]
        ms.add(a[i])
        cnt += 1
    else:
        if ms[0] < a[i]:
            su += a[i] - ms[0]
            ms.discard(ms[0])
            ms.add(a[i])

print(ans)
0