結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    M = int(input[idx])
    idx +=1
    A = []
    B = []
    C = []
    for _ in range(N):
        a = int(input[idx])
        b = int(input[idx+1])
        c = int(input[idx+2])
        A.append(a)
        B.append(b)
        C.append(c)
        idx +=3

    # Preprocess each group's possible B candidates
    group_candidates = [[] for _ in range(N)]
    all_B = B.copy()
    M_i_list = []
    for i in range(N):
        a = A[i]
        c = C[i]
        mi = max(a, c)
        min_ac = min(a, c)
        M_i_list.append(mi)
        for bj_idx in range(N):
            bj = all_B[bj_idx]
            if bj > mi:
                if bj != a and bj != c:
                    group_candidates[i].append(bj_idx)
            else:
                if (a < c and bj < a) or (a > c and bj < c):
                    if bj != a and bj != c:
                        group_candidates[i].append(bj_idx)

    # Build bipartite graph for perfect matching check
    graph = [[] for _ in range(N)]
    for i in range(N):
        for bj_idx in group_candidates[i]:
            graph[i].append(bj_idx)

    # Hopcroft-Karp algorithm for bipartite 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 graph[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 graph[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 possible sum
    sum_M = sum(M_i_list)
    extra_candidates = []
    for i in range(N):
        a = A[i]
        c = C[i]
        mi = M_i_list[i]
        for bj_idx in group_candidates[i]:
            bj = all_B[bj_idx]
            if bj > mi:
                extra = bj - mi
                extra_candidates.append((-extra, i, bj_idx))  # use negative for min heap

    # Sort by descending extra
    extra_candidates.sort()

    group_used = [False] * N
    B_used = [False] * N
    total_extra = 0

    for ec in extra_candidates:
        extra = -ec[0]
        i = ec[1]
        bj_idx = ec[2]
        if not group_used[i] and not B_used[bj_idx]:
            group_used[i] = True
            B_used[bj_idx] = True
            total_extra += extra

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

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