結果

問題 No.3509 Get More Money
コンテスト
ユーザー Shiny
提出日時 2026-04-18 00:25:11
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
RE  
実行時間 -
コード長 1,966 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 684 ms
コンパイル使用メモリ 20,824 KB
実行使用メモリ 56,900 KB
最終ジャッジ日時 2026-04-18 00:25:59
合計ジャッジ時間 46,845 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import heapq

input = sys.stdin.readline


def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n, k = map(int, input().split())
        days = [tuple(map(int, input().split())) for _ in range(n)]

        cnt = {}
        low = []
        high = []
        kept = 0
        profit = 0

        def add(value, num):
            nonlocal kept
            if num <= 0:
                return
            cnt[value] = cnt.get(value, 0) + num
            kept += num
            heapq.heappush(low, value)
            heapq.heappush(high, -value)

        def clean_low():
            while low and cnt.get(low[0], 0) == 0:
                heapq.heappop(low)

        def clean_high():
            while high and cnt.get(-high[0], 0) == 0:
                heapq.heappop(high)

        def use_buy(cost, limit):
            nonlocal kept, profit
            used = 0
            while used < limit:
                clean_high()
                if not high:
                    break
                value = -high[0]
                if value <= cost:
                    break

                have = cnt[value]
                take = min(have, limit - used)

                cnt[value] = have - take
                kept -= take
                used += take
                profit += (value - cost) * take

            if used:
                add(cost, used)

        def trim_small(extra):
            nonlocal kept
            while extra > 0:
                clean_low()
                value = low[0]
                have = cnt[value]
                drop = min(have, extra)
                cnt[value] = have - drop
                kept -= drop
                extra -= drop

        for a, b, c, d in reversed(days):
            add(c, d)
            use_buy(a, b)
            if kept > k:
                trim_small(kept - k)

        out.append(str(profit))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()
0