結果

問題 No.1430 Coup de Coupon
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:48:34
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,615 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 82,312 KB
実行使用メモリ 856,948 KB
最終ジャッジ日時 2025-06-12 20:50:46
合計ジャッジ時間 4,662 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0