結果

問題 No.568 じゃんじゃん　落とす　委員会
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:50:26
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,994 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 81,784 KB
実行使用メモリ 154,736 KB
最終ジャッジ日時 2025-04-15 21:52:09
合計ジャッジ時間 4,864 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    m = int(input[idx+1])
    idx +=2
    participants = []
    for _ in range(n):
        xi = int(input[idx])
        ai = int(input[idx+1])
        bi = int(input[idx+2])
        participants.append( (xi, ai, bi) )
        idx +=3

    # Preprocess all distinct Ai values, sorted in decreasing order
    ai_values = set()
    for xi, ai, bi in participants:
        ai_values.add(ai)
    ai_values.add(0)
    ai_values.add(100001)
    sorted_ai = sorted(ai_values, reverse=True)

    min_sum3 = float('inf')

    for SA in sorted_ai:
        group1_count = 0
        group2_count = 0
        group3_A_ok_1 = []
        group3_A_ok_0 = []
        group4_A_ok_1 = []
        group2_A_ok_1 = []
        group2_A_ok_0 = []

        for p in participants:
            xi, ai, bi = p
            if xi >=3:
                group1_count +=1
            elif xi ==2:
                group2_count +=1
                if ai >= SA:
                    group2_A_ok_1.append(bi)
                else:
                    group2_A_ok_0.append(bi)
            elif xi ==1:
                if ai >= SA:
                    group3_A_ok_1.append(bi)
                else:
                    group3_A_ok_0.append(bi)
            else: # xi ==0
                if ai >= SA:
                    group4_A_ok_1.append(bi)

        m_prime = m - (group1_count + group2_count)
        if m_prime <0:
            m_prime =0

        # Compute group3_A_ok_1_count (number of group3_A_ok_1 participants)
        group3_A_ok_1_count = len(group3_A_ok_1)
        # Compute group3_A_ok_0 and group4_A_ok_1 merged Bi
        merged_bi = group3_A_ok_0.copy()
        merged_bi.extend(group4_A_ok_1)
        merged_bi.sort()

        required = m_prime - group3_A_ok_1_count
        if required <=0:
            # SB can be as large as possible
            sum3 = group1_count + len(group2_A_ok_1)
            if sum3 < min_sum3:
                min_sum3 = sum3
            continue

        # Binary search for the largest SB where merged_bi has >= required elements >= SB
        low = 0
        high = 100001
        best_sb = 0
        while low <= high:
            mid = (low + high) //2
            cnt = len(merged_bi) - bisect.bisect_left(merged_bi, mid)
            if cnt >= required:
                best_sb = mid
                low = mid +1
            else:
                high = mid -1

        # Now compute sum3
        group2_A_ok_0_count = 0
        for bi in group2_A_ok_0:
            if bi >= best_sb:
                group2_A_ok_0_count +=1
        group3_A_ok_1_count = 0
        for bi in group3_A_ok_1:
            if bi >= best_sb:
                group3_A_ok_1_count +=1
        sum3 = group1_count + len(group2_A_ok_1) + group2_A_ok_0_count + group3_A_ok_1_count
        if sum3 < min_sum3:
            min_sum3 = sum3

    print(min_sum3)

if __name__ == '__main__':
    main()
0