結果

問題 No.200 カードファイト！
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:37:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,195 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 76,992 KB
最終ジャッジ日時 2025-04-15 22:38:28
合計ジャッジ時間 2,521 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

class Edge:
    def __init__(self, to, rev, capacity):
        self.to = to
        self.rev = rev
        self.capacity = capacity

class Dinic:
    def __init__(self, n):
        self.size = n
        self.graph = [[] for _ in range(n)]
    
    def add_edge(self, fr, to, cap):
        forward = Edge(to, len(self.graph[to]), cap)
        backward = Edge(fr, len(self.graph[fr]), 0)
        self.graph[fr].append(forward)
        self.graph[to].append(backward)
    
    def bfs_level(self, s, t, level):
        q = deque()
        level[:] = [-1] * self.size
        level[s] = 0
        q.append(s)
        while q:
            v = q.popleft()
            for edge in self.graph[v]:
                if edge.capacity > 0 and level[edge.to] == -1:
                    level[edge.to] = level[v] + 1
                    q.append(edge.to)
                    if edge.to == t:
                        return
    
    def dfs_flow(self, v, t, flow, level, ptr):
        if v == t:
            return flow
        while ptr[v] < len(self.graph[v]):
            edge = self.graph[v][ptr[v]]
            if edge.capacity > 0 and level[v] < level[edge.to]:
                min_flow = min(flow, edge.capacity)
                result = self.dfs_flow(edge.to, t, min_flow, level, ptr)
                if result > 0:
                    edge.capacity -= result
                    self.graph[edge.to][edge.rev].capacity += result
                    return result
            ptr[v] += 1
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        level = [-1] * self.size
        while True:
            self.bfs_level(s, t, level)
            if level[t] == -1:
                return flow
            ptr = [0] * self.size
            while True:
                f = self.dfs_flow(s, t, float('inf'), level, ptr)
                if f == 0:
                    break
                flow += f
            level = [-1] * self.size
        return flow

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    A = int(input[ptr])
    ptr += 1
    B = list(map(int, input[ptr:ptr + A]))
    ptr += A
    C = int(input[ptr])
    ptr += 1
    D = list(map(int, input[ptr:ptr + C]))
    ptr += C
    
    B.sort(reverse=True)
    D.sort()
    
    a = A
    a_usage = []
    base = N // a
    rem = N % a
    for i in range(a):
        a_usage.append(base + 1 if i < rem else base)
    
    c = C
    c_usage = []
    base_c = N // c
    rem_c = N % c
    for i in range(c):
        c_usage.append(base_c + 1 if i < rem_c else base_c)
    
    num_a = len(B)
    num_c = len(D)
    total_nodes = 2 + num_a + num_c
    dinic = Dinic(total_nodes)
    source = 0
    sink = num_a + num_c + 1
    
    for i in range(num_a):
        dinic.add_edge(source, i + 1, a_usage[i])
    
    for j in range(num_c):
        dinic.add_edge(num_a + 1 + j, sink, c_usage[j])
    
    for i in range(num_a):
        for j in range(num_c):
            if B[i] > D[j]:
                dinic.add_edge(i + 1, num_a + 1 + j, float('inf'))
    
    print(dinic.max_flow(source, sink))

if __name__ == '__main__':
    main()
0