結果

問題 No.2713 Just Solitaire
ユーザー detteiuudetteiuu
提出日時 2024-10-08 08:38:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 108 ms / 2,000 ms
コード長 2,390 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 78,592 KB
最終ジャッジ日時 2024-10-08 08:38:37
合計ジャッジ時間 3,932 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
54,528 KB
testcase_01 AC 37 ms
54,656 KB
testcase_02 AC 46 ms
61,568 KB
testcase_03 AC 106 ms
76,500 KB
testcase_04 AC 94 ms
77,916 KB
testcase_05 AC 56 ms
64,128 KB
testcase_06 AC 95 ms
77,400 KB
testcase_07 AC 53 ms
63,616 KB
testcase_08 AC 60 ms
55,040 KB
testcase_09 AC 44 ms
60,928 KB
testcase_10 AC 47 ms
63,104 KB
testcase_11 AC 68 ms
74,284 KB
testcase_12 AC 55 ms
67,672 KB
testcase_13 AC 88 ms
77,412 KB
testcase_14 AC 81 ms
77,332 KB
testcase_15 AC 40 ms
55,168 KB
testcase_16 AC 52 ms
64,512 KB
testcase_17 AC 84 ms
76,980 KB
testcase_18 AC 44 ms
55,040 KB
testcase_19 AC 92 ms
77,568 KB
testcase_20 AC 42 ms
55,376 KB
testcase_21 AC 39 ms
55,040 KB
testcase_22 AC 49 ms
64,000 KB
testcase_23 AC 81 ms
77,572 KB
testcase_24 AC 108 ms
78,184 KB
testcase_25 AC 98 ms
78,132 KB
testcase_26 AC 91 ms
78,524 KB
testcase_27 AC 94 ms
78,108 KB
testcase_28 AC 96 ms
78,336 KB
testcase_29 AC 92 ms
78,592 KB
testcase_30 AC 98 ms
78,080 KB
testcase_31 AC 89 ms
78,240 KB
testcase_32 AC 102 ms
78,592 KB
testcase_33 AC 96 ms
77,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from types import GeneratorType
from collections import deque

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to
    return wrappedfunc

class Dinic_edge:
    def __init__(self, t, cap, rev):
        self.t = t
        self.cap = cap
        self.rev = rev

class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for _ in range(N)]
    
    def add_edge(self, u, v, cap):
        self.G[u].append(Dinic_edge(v, cap, len(self.G[v])))
        self.G[v].append(Dinic_edge(u, 0, len(self.G[u])-1))
    
    def bfs(self, s, to):
        self.level = [-1]*self.N
        que = deque()
        que.append(s)
        self.level[s] = 0
        while que:
            n = que.popleft()
            for v in self.G[n]:
                if v.cap and self.level[v.t] == -1:
                    self.level[v.t] = self.level[n]+1
                    que.append(v.t)
        return self.level[to] != -1

    @bootstrap
    def dfs(self, n, to, f):
        if n == to:
            yield f
        for v in self.it[n]:
            if v.cap and self.level[n] < self.level[v.t]:
                d = yield self.dfs(v.t, to, min(f, v.cap))
                if d:
                    v.cap -= d
                    self.G[v.t][v.rev].cap += d
                    yield d
        yield 0
    
    def flow(self, s, t):
        flow = 0
        INF = 10**18
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
bonus = [list(map(int, input().split()))[1:] for _ in range(M)]

D = Dinic(N+2+M)
INF = 10**18
for i in range(N):
    D.add_edge(N+M, i, A[i])
    D.add_edge(i, N+M+1, 0)
for i, C in enumerate(bonus):
    for c in C:
        D.add_edge(c-1, N+i, INF)
for i in range(M):
    D.add_edge(N+i, N+M+1, B[i])

print(-(D.flow(N+M, N+M+1)-sum(B)))
0