結果

問題 No.2957 Combo Deck Builder
ユーザー navel_tos
提出日時 2025-01-11 17:10:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 591 ms / 1,000 ms
コード長 2,624 bytes
コンパイル時間 2,045 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 145,492 KB
最終ジャッジ日時 2025-01-11 17:11:21
合計ジャッジ時間 20,944 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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):
#
#CiYi CiXi
# (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):
#:
#CiYiXi A
#
#: sum(Xi) + max( Yi - Xi )
#Ci - 1Yi → 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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0