結果

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

ソースコード

diff #
raw source code 

import sys
import heapq


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    t = data[0]
    idx = 1
    ans = []

    for _ in range(t):
        n = data[idx]
        k = data[idx + 1]
        idx += 2

        a = data[idx:idx + n]
        idx += n
        b = data[idx:idx + n]
        idx += n
        c = data[idx:idx + n]
        idx += n
        d = data[idx:idx + n]
        idx += n

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

        def add(value, num):
            nonlocal total
            if num <= 0:
                return
            cnt[value] = cnt.get(value, 0) + num
            total += 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 total, 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
                total -= take
                used += take
                profit += (value - cost) * take

            if used:
                add(cost, used)

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

        for i in range(n - 1, -1, -1):
            add(c[i], d[i])
            use_buy(a[i], b[i])
            if total > k:
                trim_small(total - k)

        ans.append(str(profit))

    sys.stdout.write('\n'.join(ans))


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