結果
問題 |
No.1341 真ん中を入れ替えて門松列
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:53:16 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,518 bytes |
コンパイル時間 | 496 ms |
コンパイル使用メモリ | 81,728 KB |
実行使用メモリ | 144,728 KB |
最終ジャッジ日時 | 2025-04-15 23:54:38 |
合計ジャッジ時間 | 4,947 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 5 TLE * 1 -- * 8 |
ソースコード
import sys import heapq from collections import defaultdict from bisect import bisect_left, bisect_right class Edge: def __init__(self, to, rev, cap, cost): self.to = to self.rev = rev self.cap = cap self.cost = cost class MinCostFlow: def __init__(self, N): self.N = N self.graph = [[] for _ in range(N)] def add_edge(self, fr, to, cap, cost): forward = Edge(to, len(self.graph[to]), cap, cost) backward = Edge(fr, len(self.graph[fr]), 0, -cost) self.graph[fr].append(forward) self.graph[to].append(backward) def flow(self, s, t, maxf): N = self.N res = 0 h = [0] * N # potential prevv = [0] * N preve = [0] * N INF = float('inf') while maxf > 0: dist = [INF] * N dist[s] = 0 heap = [] heapq.heappush(heap, (0, s)) while heap: d, v = heapq.heappop(heap) if dist[v] < d: continue for i, e in enumerate(self.graph[v]): if e.cap > 0 and dist[e.to] > d + e.cost + h[v] - h[e.to]: dist[e.to] = d + e.cost + h[v] - h[e.to] prevv[e.to] = v preve[e.to] = i heapq.heappush(heap, (dist[e.to], e.to)) if dist[t] == INF: return -1 # no more flow for v in range(N): h[v] += dist[v] if dist[v] < INF else 0 d = maxf v = t while v != s: d = min(d, self.graph[prevv[v]][preve[v]].cap) v = prevv[v] maxf -= d res += d * h[t] v = t while v != s: e = self.graph[prevv[v]][preve[v]] e.cap -= d self.graph[v][e.rev].cap += d v = prevv[v] return res def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 M = int(input[ptr]) ptr += 1 groups = [] all_B = [] 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, B, C)) all_B.append(B) B_count = defaultdict(int) for b in all_B: B_count[b] += 1 sorted_B = sorted(B_count.keys()) K = len(sorted_B) B_to_idx = {b: i for i, b in enumerate(sorted_B)} S = [] possible = True for i in range(N): A_i, _, C_i = groups[i] candidates = [] if A_i < C_i: left = bisect_left(sorted_B, A_i) for b in sorted_B[:left]: if b != A_i and b != C_i: candidates.append(b) right = bisect_right(sorted_B, C_i) for b in sorted_B[right:]: if b != A_i and b != C_i: candidates.append(b) else: left = bisect_left(sorted_B, C_i) for b in sorted_B[:left]: if b != A_i and b != C_i: candidates.append(b) right = bisect_right(sorted_B, A_i) for b in sorted_B[right:]: if b != A_i and b != C_i: candidates.append(b) valid_b = [] for b in candidates: vals = sorted([A_i, b, C_i]) if vals[1] == A_i or vals[1] == C_i: valid_b.append(b) if not valid_b: possible = False S.append(valid_b) if not possible: print("NO") return total_nodes = 1 + N + K + 1 mcf = MinCostFlow(total_nodes) S_node = 0 T_node = 1 + N + K for i in range(N): mcf.add_edge(S_node, 1 + i, 1, 0) for i in range(N): A_i, _, C_i = groups[i] for b in S[i]: p = max(A_i, b, C_i) b_idx = 1 + N + B_to_idx[b] mcf.add_edge(1 + i, b_idx, 1, -p) for idx, b in enumerate(sorted_B): b_idx = 1 + N + idx cap = B_count[b] mcf.add_edge(b_idx, T_node, cap, 0) total_cost = mcf.flow(S_node, T_node, N) if total_cost == -1: print("NO") return sum_p = -total_cost if sum_p >= M: print("YES") print("KADOMATSU!") else: print("YES") print("NO") if __name__ == "__main__": main()