結果

問題 No.2028 Even Choice
ユーザー siganaisiganai
提出日時 2022-08-05 21:52:41
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,757 bytes
コンパイル時間 592 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 111,624 KB
最終ジャッジ日時 2024-09-15 18:20:54
合計ジャッジ時間 7,367 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 429 ms
109,312 KB
testcase_01 AC 440 ms
109,568 KB
testcase_02 AC 399 ms
109,568 KB
testcase_03 AC 219 ms
109,928 KB
testcase_04 AC 211 ms
109,312 KB
testcase_05 AC 233 ms
82,680 KB
testcase_06 AC 387 ms
111,624 KB
testcase_07 AC 246 ms
85,856 KB
testcase_08 AC 278 ms
100,880 KB
testcase_09 AC 362 ms
104,848 KB
testcase_10 AC 188 ms
84,952 KB
testcase_11 AC 215 ms
81,664 KB
testcase_12 AC 168 ms
80,208 KB
testcase_13 AC 343 ms
107,688 KB
testcase_14 AC 232 ms
85,580 KB
testcase_15 AC 65 ms
68,096 KB
testcase_16 AC 65 ms
67,712 KB
testcase_17 AC 64 ms
67,456 KB
testcase_18 AC 65 ms
67,712 KB
testcase_19 AC 68 ms
68,480 KB
testcase_20 AC 77 ms
71,936 KB
testcase_21 AC 77 ms
72,832 KB
testcase_22 AC 74 ms
71,168 KB
testcase_23 RE -
testcase_24 AC 66 ms
67,328 KB
testcase_25 RE -
testcase_26 AC 64 ms
67,712 KB
testcase_27 AC 64 ms
68,096 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