結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー lam6er
提出日時 2025-03-26 15:49:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,899 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 113,272 KB
最終ジャッジ日時 2025-03-26 15:50:10
合計ジャッジ時間 4,432 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

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

import bisect
def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n, m = int(input[idx]), int(input[idx+1])
    idx += 2
    
    C1 = 0
    C2_ai_bi = []
    C3_ai_bi = []
    C4_ai_bi = []
    
    for _ in range(n):
        xi = int(input[idx])
        ai = int(input[idx+1])
        bi = int(input[idx+2])
        idx +=3
        if xi >=3:
            C1 +=1
        elif xi == 2:
            C2_ai_bi.append( (ai, bi) )
        elif xi ==1:
            C3_ai_bi.append( (ai, bi) )
        elif xi ==0:
            C4_ai_bi.append( (ai, bi) )
    
    C2_count = len(C2_ai_bi)
    total_C1C2 = C1 + C2_count
    if m <= total_C1C2:
        print(C1)
        return
    
    need = m - total_C1C2
    
    possible_SA = set()
    for ai, _ in C3_ai_bi:
        possible_SA.add(ai)
    for ai, _ in C4_ai_bi:
        possible_SA.add(ai)
    possible_SA = sorted(possible_SA)
    possible_SA.append(100001 +2)
    
    min_increment = float('inf')
    
    for SA_candidate in possible_SA:
        C3_a_list = []
        C3_not_a_bi = []
        for ai, bi in C3_ai_bi:
            if ai >= SA_candidate:
                C3_a_list.append(bi)
            else:
                C3_not_a_bi.append(bi)
        c3_a = len(C3_a_list)
        C4_a_bi = [bi for ai, bi in C4_ai_bi if ai >= SA_candidate]
        
        need_remaining = need - c3_a
        if need_remaining <=0:
            C2_a = sum(1 for ai, _ in C2_ai_bi if ai >= SA_candidate)
            increment = C2_a
            if increment < min_increment:
                min_increment = increment
            continue
        
        C3_not_a_sorted = sorted(C3_not_a_bi)
        C4_a_sorted = sorted(C4_a_bi)
        
        low = 0
        high = 100001
        best_x = -1
        while low <= high:
            mid = (low + high) //2
            cnt3 = len(C3_not_a_sorted) - bisect.bisect_left(C3_not_a_sorted, mid)
            cnt4 = len(C4_a_sorted) - bisect.bisect_left(C4_a_sorted, mid)
            if cnt3 + cnt4 >= need_remaining:
                best_x = mid
                low = mid +1
            else:
                high = mid -1
        if best_x == -1:
            continue
        
        C2_not_a_bi = [bi for ai, bi in C2_ai_bi if ai < SA_candidate]
        C2_not_a_sorted = sorted(C2_not_a_bi)
        cnt_c2_not_a = len(C2_not_a_sorted) - bisect.bisect_left(C2_not_a_sorted, best_x)
        
        C3_both_sorted = sorted(C3_a_list)
        cnt_c3_both = len(C3_both_sorted) - bisect.bisect_left(C3_both_sorted, best_x)
        
        C2_a = sum(1 for ai, _ in C2_ai_bi if ai >= SA_candidate)
        increment = C2_a + cnt_c2_not_a + cnt_c3_both
        
        if increment < min_increment:
            min_increment = increment
    
    if min_increment == float('inf'):
        print(-1)
    else:
        print(C1 + min_increment)
if __name__ == "__main__":
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0