結果

問題 No.1341 真ん中を入れ替えて門松列
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:56:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,298 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 226,908 KB
最終ジャッジ日時 2025-06-12 20:59:38
合計ジャッジ時間 4,513 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 5 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1

    groups = []
    Bs = []
    for _ in range(N):
        A = int(data[idx])
        B = int(data[idx+1])
        C = int(data[idx+2])
        idx +=3
        groups.append((A, B, C))
        Bs.append(B)
    
    for i in range(N):
        A, B, C = groups[i]
        if A == C:
            print("NO")
            return

    min_i = []
    max_i = []
    for A, B, C in groups:
        mi = min(A, C)
        ma = max(A, C)
        min_i.append(mi)
        max_i.append(ma)
    
    possible = [[] for _ in range(N)]
    for i in range(N):
        mi = min_i[i]
        ma = max_i[i]
        for j in range(N):
            b = Bs[j]
            if (b < mi) or (b > ma):
                possible[i].append(j)
        if not possible[i]:
            print("NO")
            return

    adj = [[] for _ in range(N)]
    for i in range(N):
        for j in possible[i]:
            adj[i].append(j)

    match_to = [-1] * N
    seen = [False] * N

    def bpm(u):
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                if match_to[v] == -1 or bpm(match_to[v]):
                    match_to[v] = u
                    return True
        return False

    result = 0
    for u in range(N):
        seen = [False] * N
        if bpm(u):
            result +=1
    if result != N:
        print("NO")
        return

    Bs_sorted = sorted(Bs, reverse=True)
    groups_sorted = sorted(enumerate(groups), key=lambda x: max(x[1][0], x[1][2]))

    sum_total = 0
    used = [False] * len(Bs_sorted)
    for i in range(N):
        A, B, C = groups_sorted[i][1]
        ma = max(A, C)
        found = False
        for j in range(len(Bs_sorted)):
            if not used[j] and Bs_sorted[j] > ma:
                sum_total += Bs_sorted[j]
                used[j] = True
                found = True
                break
        if not found:
            sum_total += ma

    if sum_total >= M:
        print("YES")
        print("KADOMATSU!")
    else:
        print("YES")
        print("NO")

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