結果

問題 No.2623 Room Allocation
コンテスト
ユーザー navel_tos
提出日時 2025-01-15 12:05:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 369 ms / 2,000 ms
コード長 815 bytes
コンパイル時間 1,349 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 157,440 KB
最終ジャッジ日時 2025-01-15 12:06:05
合計ジャッジ時間 9,903 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder22623 Room Allocation

#入力受取
N, X, Y = map(int, input().split())
custs = [input().split() for _ in range(N)]

#Z = X + Y とすると、Zグループ周期で同じ部屋に案内される
#DP[z][f]: z % Zグループ目が希望する機械がf = 0, 1: A, B である
Z = X + Y
DP = [[0] * 2 for _ in range(Z)]
for i, (Pi, Ci) in enumerate( custs ):
    DP[i % Z][Ci == 'B'] += int(Pi)

#読み替え後の問題は以下の通り:
#Zグループ、利得はDP[z][0, 1]から選べる。0をちょうどX個、1をY個選ぶときの最大利得
#全員0を選んでおいて、(DP[z][1] - DP[z][0])の大きい側YグループをYに移籍すればよい
ans = sum(DP[z][0] for z in range(Z))
Q = sorted([ DP[z][1] - DP[z][0] for z in range(Z) ])
print( ans + sum( Q[- Y:] ) if Y > 0 else ans )
0