結果
問題 |
No.1341 真ん中を入れ替えて門松列
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()