ABC312 F — Cans and Openers

1# -*- coding: utf-8 -*-2 3 4from heapq import heapify, heappop, heappush5from typing import List, Optional6 7 8class DeletableHeapq:9    """Alternatives to ordered set (set) in C++.10 11    Landau notation: O(log(n))12 13    See:14    https://qiita.com/physharp/items/f9229ab879cac9a944d715    https://prd-xxx.hateblo.jp/entry/2019/06/24/23584416    """17 18    def __init__(self, descending_order=False) -> None:19        self.q: List[int] = []  # Body20        self.p: List[int] = []  # For deleting21        self.descending_order = descending_order22        self.sign = -1 if descending_order else 123 24    def build(self, a: List[int]) -> None:25        """Build a priority-queue q from an array."""26 27        if self.descending_order:28            a = [-ai for ai in a]29 30        self.q = a31        heapify(self.q)32 33    def push(self, number: int) -> None:34        """Add a number to the priority-queue."""35        heappush(self.q, number * self.sign)36 37    def erase(self, number: int) -> None:38        """Pseudo-erase a number to the priority-queue."""39        heappush(self.p, number * self.sign)40        self.clean()41 42    def clean(self) -> None:43        """Remove top elements from q, p."""44 45        while self.p and self.q[0] == self.p[0]:46            heappop(self.q)47            heappop(self.p)48 49    def pop(self, exc=None) -> Optional[int]:50        """Pop a top value from the priority-queue."""51        self.clean()52 53        if self.q:54            return heappop(self.q) * self.sign55        return exc56 57    def top(self, exc=None) -> Optional[int]:58        """Get a top value from the priority-queue.59 60        Landau notation: O(1)61 62        Note:63        descending_order=False: min value.64        descending_order=True : max value.65        """66        self.clean()67 68        if self.q:69            return self.q[0] * self.sign70        return exc71 72 73def main():74    import sys75 76    input = sys.stdin.readline77 78    n, m = map(int, input().split())79    cans0 = DeletableHeapq()80    cans1, openers = list(), list()81    summed = 082 83    # 品物の種類別に入力を受け取る84    for _ in range(n):85        ti, xi = map(int, input().split())86 87        if ti == 0:88            cans0.push(xi)89            summed += xi90        elif ti == 1:91            cans1.append(xi)92        else:93            openers.append(xi)94 95    # 缶切りが不要な品物がm個よりも多い場合への対処96    while len(cans0.q) > m:97        value = cans0.pop()98        summed -= value99 100    # print(summed)101 102    cans1.sort()103    openers.sort(reverse=True)104    item_count = m105    ans = summed106 107    # 使用できる缶が多い缶切りを使って、缶切りが必要な缶を使う108    for opener_count in openers:109        item_count -= 1110 111        if item_count == 0:112            break113 114        for _ in range(opener_count):115            if len(cans1) == 0:116                break117 118            tmp = cans1.pop()119            cans0.push(tmp)120            summed += tmp121 122        while len(cans0.q) > item_count:123            tmp = cans0.pop()124            summed -= tmp125 126        ans = max(ans, summed)127 128    # print(cans1, openers)129    print(ans)130 131 132if __name__ == "__main__":133    main()134