結果

問題 No.3459 Defeat Slimes
コンテスト
ユーザー koheijkt
提出日時 2026-03-01 13:56:04
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 620 ms / 3,000 ms
コード長 2,087 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,333 ms
コンパイル使用メモリ 85,140 KB
実行使用メモリ 122,440 KB
最終ジャッジ日時 2026-03-01 13:56:25
合計ジャッジ時間 18,866 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys, math
sys.setrecursionlimit(10**8)
sys.set_int_max_str_digits(0)
INF = 1e18
MOD = 998244353
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import product, combinations, permutations, groupby, accumulate
from heapq import heapify, heappop, heappush
input = sys.stdin.readline
def I():   return input().rstrip()
def II():  return int(input().rstrip())
def IS():  return input().rstrip().split()
def MII(): return map(int, input().rstrip().split())
def LI():  return list(input().rstrip())
def TII(): return tuple(map(int, input().rstrip().split()))
def LII(): return list(map(int, input().rstrip().split()))
def LSI(): return list(map(str, input().rstrip().split()))
def GMI(): return list(map(lambda x: int(x) - 1, input().rstrip().split()))
def kiriage(a, b): return (a+b-1)//b

N, Y, Z = MII()
C, L, X = [], [], []
for i in range(N):
    c, l, x = MII()
    C.append(c)
    L.append(l)
    X.append(x)

border = [(L[i], i) for i in range(N)]
border.append((Z, -1))
border.sort()

pq = []
# Y以下のレベルは que に追加
for i in range(N):
    if L[i] <= Y:
        heappush(pq, (-X[i], C[i]))

k = bisect_right(border, (Y, INF))
# 初期状態の k は Y超過の最小レベルを持つモンスターを指している
cur = Y
ans = 0
while pq and cur < Z:
    # 次の解放イベント
    nxt, idx = border[k]
    if nxt <= cur: # イコールとしないのは、nxt をオーバーランしていることがあるため   
        if idx != -1:    
            heappush(pq, (-X[idx], C[idx]))
            k += 1
        # while文もういちど回す = 今のレベルで解放できるイベントは全部済ませる
        continue

    x, c = heappop(pq)
    x = -x
    # このモンスターを狩り尽くすか、次の解放イベントまで狩る
    cnt = min(c, kiriage(nxt - cur, x))
    # レベル、個数の計算
    cur += x * cnt
    ans += cnt
    if cnt != c: # 残存したら戻す
        heappush(pq, (-x, c - cnt))

if cur >= Z:
    print(ans)
else:
    print(-1)
0