結果
問題 |
No.1430 Coup de Coupon
|
ユーザー |
![]() |
提出日時 | 2025-06-12 15:26:50 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 3,615 bytes |
コンパイル時間 | 151 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 857,008 KB |
最終ジャッジ日時 | 2025-06-12 15:27:15 |
合計ジャッジ時間 | 4,595 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 MLE * 1 -- * 20 |
ソースコード
import sys from collections import deque class Edge: def __init__(self, to, rev, capacity, cost): self.to = to self.rev = rev self.capacity = capacity self.cost = cost class MinCostFlow: def __init__(self, N): self.N = N self.graph = [[] for _ in range(N)] def add_edge(self, fr, to, capacity, cost): forward = Edge(to, len(self.graph[to]), capacity, 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 inqueue = [False] * N dist[s] = 0 q = deque() q.append(s) inqueue[s] = True while q: v = q.popleft() inqueue[v] = False for i, e in enumerate(self.graph[v]): if e.capacity > 0 and dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]: dist[e.to] = dist[v] + e.cost + h[v] - h[e.to] prevv[e.to] = v preve[e.to] = i if not inqueue[e.to]: q.append(e.to) inqueue[e.to] = True if dist[t] == INF: return res 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]].capacity) v = prevv[v] maxf -= d res += d * h[t] v = t while v != s: e = self.graph[prevv[v]][preve[v]] e.capacity -= d self.graph[v][e.rev].capacity += d v = prevv[v] return res def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 C = int(input[ptr]) ptr += 1 P = [] for _ in range(N): P.append(int(input[ptr])) ptr += 1 sum_P = sum(P) coupons = [] for _ in range(C): T = int(input[ptr]) ptr += 1 X = int(input[ptr]) ptr += 1 coupons.append( (T, X) ) # Create the flow network # Nodes: # 0: source # 1..C: coupons # C+1..C+N: items # C+N+1: sink total_nodes = 1 + C + N + 1 source = 0 sink = C + N + 1 mcf = MinCostFlow(total_nodes) # Add edges from source to coupons for j in range(1, C+1): mcf.add_edge(source, j, 1, 0) # Add edges from items to sink for i in range(C+1, C+N+1): mcf.add_edge(i, sink, 1, 0) # Precompute S_ji for each coupon j and item i for j in range(C): T, X = coupons[j] j_node = j + 1 # since source is 0, coupons start at 1 for i in range(N): P_i = P[i] if T == 1: S_ji = min(X, P_i) else: S_ji = (X * P_i) // 100 i_node = C + 1 + i # Add edge from coupon j to item i with cost -S_ji mcf.add_edge(j_node, i_node, 1, -S_ji) K = min(C, N) cost_flow = mcf.flow(source, sink, K) total_cost = sum_P + cost_flow print(total_cost) if __name__ == '__main__': main()