結果

問題 No.1341 真ん中を入れ替えて門松列
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:33:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,713 bytes
コンパイル時間 214 ms
コンパイル使用メモリ 82,968 KB
実行使用メモリ 72,064 KB
最終ジャッジ日時 2025-06-12 16:33:37
合計ジャッジ時間 2,497 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    groups = []
    B_list = []
    for _ in range(N):
        A = int(input[ptr])
        ptr += 1
        B = int(input[ptr])
        ptr += 1
        C = int(input[ptr])
        ptr += 1
        groups.append((A, C))
        B_list.append(B)

    # Precompute lower and upper for each group
    lower = []
    upper = []
    for A, C in groups:
        lower_i = min(A, C)
        upper_i = max(A, C)
        lower.append(lower_i)
        upper.append(upper_i)

    # Check if any group has no possible B_j
    possible = True
    for i in range(N):
        has_possible = False
        for B_j in B_list:
            if B_j < lower[i] or B_j > upper[i]:
                has_possible = True
                break
        if not has_possible:
            possible = False
            break
    if not possible:
        print("NO")
        return

    sum_upper = sum(upper)

    # Sort groups by upper_i in ascending order
    sorted_groups = sorted([(upper[i], i) for i in range(N)], key=lambda x: x[0])
    group_order = [i for (u, i) in sorted_groups]

    # Sort B's in descending order
    sorted_B = sorted(B_list, reverse=True)

    assigned = [False] * N
    sum_gain = 0

    for B in sorted_B:
        for idx in group_order:
            if not assigned[idx] and B > upper[idx]:
                sum_gain += (B - upper[idx])
                assigned[idx] = True
                break

    total = sum_upper + sum_gain

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

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