結果

問題 No.1678 Coin Trade (Multiple)
ユーザー chocoruskchocorusk
提出日時 2021-08-02 03:30:57
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,958 bytes
コンパイル時間 273 ms
コンパイル使用メモリ 86,920 KB
実行使用メモリ 196,636 KB
最終ジャッジ日時 2023-09-02 15:06:49
合計ジャッジ時間 77,759 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 78 ms
71,508 KB
testcase_01 AC 80 ms
71,228 KB
testcase_02 AC 81 ms
71,228 KB
testcase_03 AC 533 ms
101,484 KB
testcase_04 AC 2,393 ms
143,680 KB
testcase_05 AC 1,067 ms
120,672 KB
testcase_06 AC 803 ms
112,280 KB
testcase_07 AC 2,236 ms
135,604 KB
testcase_08 AC 1,432 ms
121,608 KB
testcase_09 AC 1,096 ms
121,756 KB
testcase_10 AC 542 ms
90,892 KB
testcase_11 AC 1,815 ms
128,040 KB
testcase_12 AC 493 ms
92,284 KB
testcase_13 AC 3,699 ms
171,172 KB
testcase_14 AC 1,247 ms
116,628 KB
testcase_15 AC 1,303 ms
121,744 KB
testcase_16 AC 423 ms
103,168 KB
testcase_17 AC 1,130 ms
121,088 KB
testcase_18 AC 99 ms
76,176 KB
testcase_19 AC 81 ms
71,380 KB
testcase_20 AC 88 ms
75,508 KB
testcase_21 AC 91 ms
75,348 KB
testcase_22 AC 97 ms
76,424 KB
testcase_23 AC 85 ms
75,148 KB
testcase_24 AC 99 ms
76,152 KB
testcase_25 AC 81 ms
71,420 KB
testcase_26 AC 97 ms
76,352 KB
testcase_27 AC 88 ms
75,648 KB
testcase_28 AC 89 ms
76,408 KB
testcase_29 AC 83 ms
71,140 KB
testcase_30 AC 85 ms
75,384 KB
testcase_31 AC 83 ms
75,136 KB
testcase_32 AC 79 ms
71,312 KB
testcase_33 AC 101 ms
76,360 KB
testcase_34 AC 93 ms
76,264 KB
testcase_35 AC 81 ms
71,184 KB
testcase_36 AC 105 ms
76,308 KB
testcase_37 AC 101 ms
76,240 KB
testcase_38 AC 89 ms
75,684 KB
testcase_39 AC 88 ms
76,148 KB
testcase_40 AC 101 ms
76,272 KB
testcase_41 AC 94 ms
76,592 KB
testcase_42 AC 104 ms
77,040 KB
testcase_43 AC 108 ms
77,184 KB
testcase_44 AC 87 ms
76,384 KB
testcase_45 AC 79 ms
71,052 KB
testcase_46 AC 109 ms
77,388 KB
testcase_47 AC 93 ms
76,092 KB
testcase_48 AC 4,724 ms
195,504 KB
testcase_49 AC 4,834 ms
194,016 KB
testcase_50 AC 4,666 ms
195,640 KB
testcase_51 AC 4,879 ms
195,976 KB
testcase_52 TLE -
testcase_53 TLE -
testcase_54 AC 4,911 ms
196,636 KB
testcase_55 AC 4,805 ms
195,676 KB
testcase_56 AC 4,810 ms
192,388 KB
testcase_57 AC 4,564 ms
195,240 KB
testcase_58 AC 2,075 ms
132,724 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines
import heapq
class MinCostFlow:
    def __init__(self, n, neg=False):
        self.n=n
        self.g=[[] for _ in range(n)]
        self.h=[0]*n
        self.neg=neg
    def add_edge(self, frm, to, cap, cost):
        g=self.g
        g[frm].append([to, cap, cost, len(g[to])])
        g[to].append([frm, 0, -cost, len(g[frm])-1])
    def bellman_ford(self, s, prevv, preve):
        n=self.n
        g=self.g
        h=self.h
        INF=10**18
        for x in range(n):
            h[x]=INF
        h[s]=0
        for _ in range(n-1):
            for x in range(n):
                for i, e in enumerate(g[x]):
                    if e[1]==0:
                        continue
                    to, cost=e[0], e[2]
                    if h[to]>h[x]+cost:
                        h[to]=h[x]+cost
                        prevv[to]=x
                        preve[to]=i
    def flow(self, s, t, f):
        res=0
        n=self.n
        g=self.g
        h=self.h
        INF=10**16
        LOG=16 #n<2**LOG
        prevv=[0]*n
        preve=[0]*n
        while f>0:
            if self.neg:
                self.neg=False
                self.bellman_ford(s, prevv, preve)
                if h[t]==INF:
                    return -1
            else:
                que=[]
                dist=[INF]*n
                dist[s]=0
                heapq.heappush(que, s)
                while que:
                    p=heapq.heappop(que)
                    v=(p&((1<<LOG)-1))
                    if dist[v]<(p>>LOG):
                        continue
                    for i, e in enumerate(g[v]):
                        if e[1]==0:
                            continue
                        to, cost=e[0], e[2]
                        if dist[to]>dist[v]+cost+h[v]-h[to]:
                            dist[to]=dist[v]+cost+h[v]-h[to]
                            prevv[to]=v
                            preve[to]=i
                            heapq.heappush(que, (dist[to]<<LOG)^to)
                for i, d in enumerate(dist):
                    h[i]+=d
                if dist[t]==INF:
                    return -1
            d=f
            v=t
            while v!=s:
                d=min(d, g[prevv[v]][preve[v]][1])
                v=prevv[v]
            f-=d
            res+=d*h[t]
            v=t
            while v!=s:
                g[prevv[v]][preve[v]][1]-=d
                rev=g[prevv[v]][preve[v]][3]
                g[v][rev][1]+=d
                v=prevv[v]
        return res
n, k=map(int, readline().split())
inf=10**9
g=MinCostFlow(n)
a=[0]*n
for i in range(n):
    a[i], m=map(int, readline().split())
    b=list(map(int, readline().split()))
    for bi in b:
        bi-=1
        g.add_edge(bi, i, 1, a[bi]-a[i]+inf*(i-bi))
for i in range(n-1):
    g.add_edge(i, i+1, k, inf)
print(inf*(n-1)*k-g.flow(0, n-1, k))
0