結果

問題 No.3509 Get More Money
コンテスト
ユーザー Ian
提出日時 2026-04-19 10:13:59
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 1,439 ms / 2,000 ms
コード長 1,802 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 492 ms
コンパイル使用メモリ 20,696 KB
実行使用メモリ 127,044 KB
最終ジャッジ日時 2026-04-19 10:15:12
合計ジャッジ時間 62,985 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import heapq
from collections import defaultdict

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    T = int(data[idx]); idx += 1
    out = []
    for _ in range(T):
        N = int(data[idx]); idx += 1
        K = int(data[idx]); idx += 1
        A = [int(x) for x in data[idx:idx+N]]; idx += N
        B = [int(x) for x in data[idx:idx+N]]; idx += N
        C = [int(x) for x in data[idx:idx+N]]; idx += N
        D = [int(x) for x in data[idx:idx+N]]; idx += N

        min_h, max_h = [], []
        cnt = defaultdict(int)
        total = 0
        profit = 0

        for i in range(N):
            a, b, c, d = A[i], B[i], C[i], D[i]
            if cnt[a] == 0:
                heapq.heappush(min_h, a)
                heapq.heappush(max_h, -a)
            cnt[a] += b
            total += b

            rem = d
            while rem > 0:
                while min_h and cnt[min_h[0]] == 0:
                    heapq.heappop(min_h)
                if not min_h: break
                p = min_h[0]
                if p >= c: break
                take = cnt[p] if cnt[p] < rem else rem
                profit += (c - p) * take
                cnt[p] -= take
                if cnt[c] == 0:
                    heapq.heappush(min_h, c)
                    heapq.heappush(max_h, -c)
                cnt[c] += take
                rem -= take

            while total > K:
                while max_h and cnt[-max_h[0]] == 0:
                    heapq.heappop(max_h)
                if not max_h: break
                p = -max_h[0]
                need = total - K
                drop = cnt[p] if cnt[p] < need else need
                cnt[p] -= drop
                total -= drop

        out.append(str(profit))
    sys.stdout.write('\n'.join(out) + '\n')

main()
0