結果

問題 No.3761 Moonlit Battle
コンテスト
ユーザー detteiuu
提出日時 2026-10-09 23:12:12
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,151 ms / 2,000 ms
+ 459µs
コード長 1,031 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 66 ms
コンパイル使用メモリ 82,812 KB
実行使用メモリ 257,296 KB
最終ジャッジ日時 2026-10-09 23:12:26
合計ジャッジ時間 10,022 ms
ジャッジサーバーID
（参考情報） 		judge5_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from sys import stdin
input = stdin.readline
from collections import defaultdict

INF = 1<<60

N, X = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

if X == 1:
    exit(print(max(b for _, b in AB)))

D = defaultdict(int)
for A, B in AB:
    D[B//X] += A
D = sorted(D.items(), key=lambda x:x[0], reverse=True)
costD = 0
SUM = 0
for n, c in D:
    SUM += c
    if X < SUM:
        costD = n
        break

ans2 = INF
for cost in range(costD-1, costD+2):
    if cost < 0: continue
    SUM = 0
    AB2 = []
    for i in range(N):
        A, B = AB[i]
        n = B//X
        if cost < n:
            SUM += A*(n-cost)
            B -= X*(n-cost)
        AB2.append([A, B])

    AB2.sort(key=lambda x:x[1], reverse=True)
    AB2.append([0, 0])
    ans = SUM+AB2[0][1]
    MAX = -1
    for i, (A, B) in enumerate(AB2[:-1]):
        if B//X < cost:
            break
        SUM += A
        MAX = max(MAX, B-X)
        ans = min(ans, SUM+max(AB2[i+1][1], MAX))
    ans2 = min(ans2, ans)

print(ans2)
0