結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    n, m = map(int, sys.stdin.readline().split())
    groups = []
    B_list = []
    for _ in range(n):
        a, b, c = map(int, sys.stdin.readline().split())
        B_list.append(b)
        max_ac = max(a, c)
        min_ac = min(a, c)
        groups.append((a, c, max_ac, min_ac))
    
    # Build adjacency list for bipartite graph
    adj = [[] for _ in range(n)]
    for i in range(n):
        a, c, max_ac, min_ac = groups[i]
        for j in range(n):
            bj = B_list[j]
            if (bj > max_ac or bj < min_ac) and bj != a and bj != c:
                adj[i].append(j)
    
    # Hopcroft-Karp algorithm to check for perfect matching
    def hopcroft_karp():
        pair_U = [-1] * n
        pair_V = [-1] * n
        dist = [0] * n
        
        def bfs():
            queue = deque()
            for u in range(n):
                if pair_U[u] == -1:
                    dist[u] = 0
                    queue.append(u)
                else:
                    dist[u] = float('inf')
            dist_null = float('inf')
            while queue:
                u = queue.popleft()
                if dist[u] < dist_null:
                    for v in adj[u]:
                        if pair_V[v] == -1:
                            dist_null = dist[u] + 1
                        elif dist[pair_V[v]] == float('inf'):
                            dist[pair_V[v]] = dist[u] + 1
                            queue.append(pair_V[v])
            return dist_null != float('inf')
        
        def dfs(u):
            for v in adj[u]:
                if pair_V[v] == -1 or (dist[pair_V[v]] == dist[u] + 1 and dfs(pair_V[v])):
                    pair_U[u] = v
                    pair_V[v] = u
                    return True
            dist[u] = float('inf')
            return False
        
        result = 0
        while bfs():
            for u in range(n):
                if pair_U[u] == -1:
                    if dfs(u):
                        result += 1
        return result == n
    
    if not hopcroft_karp():
        print("NO")
        return
    
    # Now calculate maximum total
    sorted_groups = sorted(range(n), key=lambda x: groups[x][2])
    sorted_B = sorted(enumerate(B_list), key=lambda x: (-x[1], x[0]))
    
    group_used = [False] * n
    B_used = [False] * n
    additional = 0
    
    for b_entry in sorted_B:
        j, bj_val = b_entry
        if B_used[j]:
            continue
        for i in sorted_groups:
            if group_used[i]:
                continue
            a, c, max_ac, min_ac = groups[i]
            if bj_val > max_ac and bj_val != a and bj_val != c:
                additional += bj_val - max_ac
                group_used[i] = True
                B_used[j] = True
                break
    
    total = sum(g[2] for g in groups) + additional
    print("YES")
    if total >= m:
        print("KADOMATSU!")
    else:
        print("NO")

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