結果

問題 No.3509 Get More Money
コンテスト
ユーザー 왕지후
提出日時 2026-04-18 14:20:16
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 1,652 ms / 2,000 ms
コード長 2,191 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 749 ms
コンパイル使用メモリ 20,868 KB
実行使用メモリ 189,256 KB
最終ジャッジ日時 2026-04-18 14:21:42
合計ジャッジ時間 75,125 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq
import sys
input = sys.stdin.buffer.read

def main():
    data = input().split()
    idx = 0
    def rd():
        nonlocal idx
        v = int(data[idx]); idx += 1
        return v
    
    T = rd()
    out = []
    
    for _ in range(T):
        N, K = rd(), rd()
        A = [rd() for _ in range(N)]
        B = [rd() for _ in range(N)]
        C = [rd() for _ in range(N)]
        D = [rd() for _ in range(N)]
        
        blocks = {}
        min_h = []
        max_h = []
        bid = 0
        total = 0
        profit = 0
        
        for i in range(N):
            a, b, c, d = A[i], B[i], C[i], D[i]
            
            # 買いブロックを追加
            blocks[bid] = b
            heapq.heappush(min_h, (a, bid))
            heapq.heappush(max_h, (-a, bid))
            total += b
            bid += 1
            
            # D[i]個まで貪欲に売る
            sold = 0
            while sold < d:
                while min_h and blocks.get(min_h[0][1], 0) == 0:
                    heapq.heappop(min_h)
                if not min_h or min_h[0][0] >= c:
                    break
                p, bk = min_h[0]
                take = min(blocks[bk], d - sold)
                profit += take * (c - p)
                blocks[bk] -= take
                total -= take
                sold += take
            
            # 後悔エントリー: 売った数だけ価格cで買い戻せる仮想オプション
            if sold > 0:
                blocks[bid] = sold
                heapq.heappush(min_h, (c, bid))
                heapq.heappush(max_h, (-c, bid))
                total += sold
                bid += 1
            
            # K超過分: 最高値から削除
            while total > K:
                while max_h and blocks.get(max_h[0][1], 0) == 0:
                    heapq.heappop(max_h)
                if not max_h:
                    break
                neg_p, bk = max_h[0]
                remove = min(blocks[bk], total - K)
                blocks[bk] -= remove
                total -= remove
        
        out.append(profit)
    
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

main()
0