結果
問題 |
No.1341 真ん中を入れ替えて門松列
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:16:10 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,056 bytes |
コンパイル時間 | 254 ms |
コンパイル使用メモリ | 82,028 KB |
実行使用メモリ | 156,356 KB |
最終ジャッジ日時 | 2025-06-12 21:16:58 |
合計ジャッジ時間 | 7,835 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 12 WA * 2 |
ソースコード
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()