#yukicoder2957 Combo Deck Builder #入力受取・assert N = int(input()) cards = [tuple(map(int, input().split())) for _ in range(N)] assert 1 <= N <= 2 * 10 ** 5 for Ci, Xi, Yi in cards: assert 0 <= Ci <= N assert 1 <= Xi <= 10 ** 9 and 1 <= Yi <= 10 ** 9 #愚直解 from itertools import permutations def brute(N, cards): ans = 0 for u in range(N + 1): for S in permutations( range(N), r = u ): cnt = 0 for d, i in enumerate(S): Ci, Xi, Yi = cards[i] cnt += Xi if Ci <= d else Yi ans = max(ans, cnt) return ans #貪欲法 import heapq def solve(N, cards): #問題を読み替える #Ciターン未満ならYiダメージ Ciターン以降ならXiダメージを与える #カードを (Yiを優先したい / Xiを優先したい) の2つの束に分割する A, B = [], [] for Ci, Xi, Yi in cards: if Xi < Yi: A.append((Ci, Xi, Yi)) else: B.append((N - Ci, Yi, Xi)) #カードの順序は A(Yi優先 左に置きたい) → B(Xi優先 右置き) と決め打って差し支えない #以降はA, B内の適切な並び順を決めればよい def calc(A): #以下の部分問題を解け: #Ciターン未満ならYiダメージ、以降ならXiダメージ の条件配列Aを与える。 #適切な割り振りを行ったときの最大ダメージを計算せよ。 #貪欲法で解く: sum(Xi) + max( 条件を満たす Yi - Xi )として計算する。 #Ci - 1ターン目にYi → Xi ターンの切り替えが行われるので、Yi - Xiをバケットソート n = len(A) E = [[] for _ in range(n)] ans = 0 for Ci, Xi, Yi in A: ans += Xi if Ci == 0: #Yiダメージは出せない → 無視 continue E[ min( n - 1, Ci - 1 ) ].append( Yi - Xi ) #日付の降順に貪欲: 割り振れるなら、最大のYi - Xiを割り振る Q = [] for d in range(n - 1, -1, -1): for x in E[d]: heapq.heappush(Q, - x) #maxheapなので正負反転する if Q: ans += - heapq.heappop(Q) return ans return calc(A) + calc(B) #実行 print( solve(N, cards) ) #ランダムテスト def test( time = 10000 ): from random import randint for _ in range(time): n = randint(1, 6) c = [(randint(0, n), randint(1, 1000), randint(1, 1000)) for _ in range(n)] assert brute(n, c) == solve(n, c)