結果
問題 | No.1288 yuki collection |
ユーザー |
![]() |
提出日時 | 2020-09-07 21:30:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,027 ms / 5,000 ms |
コード長 | 2,248 bytes |
コンパイル時間 | 552 ms |
コンパイル使用メモリ | 87,004 KB |
実行使用メモリ | 97,600 KB |
最終ジャッジ日時 | 2023-09-10 13:42:50 |
合計ジャッジ時間 | 100,895 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 86 ms
75,496 KB |
testcase_01 | AC | 79 ms
71,184 KB |
testcase_02 | AC | 89 ms
76,040 KB |
testcase_03 | AC | 139 ms
77,780 KB |
testcase_04 | AC | 78 ms
71,460 KB |
testcase_05 | AC | 83 ms
75,468 KB |
testcase_06 | AC | 130 ms
77,856 KB |
testcase_07 | AC | 90 ms
76,324 KB |
testcase_08 | AC | 142 ms
78,124 KB |
testcase_09 | AC | 137 ms
77,472 KB |
testcase_10 | AC | 146 ms
77,596 KB |
testcase_11 | AC | 136 ms
77,904 KB |
testcase_12 | AC | 141 ms
77,760 KB |
testcase_13 | AC | 3,657 ms
93,660 KB |
testcase_14 | AC | 3,534 ms
92,392 KB |
testcase_15 | AC | 2,846 ms
90,032 KB |
testcase_16 | AC | 2,841 ms
89,604 KB |
testcase_17 | AC | 3,927 ms
94,888 KB |
testcase_18 | AC | 3,551 ms
93,320 KB |
testcase_19 | AC | 3,560 ms
93,100 KB |
testcase_20 | AC | 3,606 ms
94,496 KB |
testcase_21 | AC | 3,293 ms
93,944 KB |
testcase_22 | AC | 3,189 ms
93,576 KB |
testcase_23 | AC | 3,435 ms
92,612 KB |
testcase_24 | AC | 3,456 ms
93,928 KB |
testcase_25 | AC | 3,631 ms
93,692 KB |
testcase_26 | AC | 3,481 ms
94,100 KB |
testcase_27 | AC | 4,027 ms
97,384 KB |
testcase_28 | AC | 4,024 ms
97,356 KB |
testcase_29 | AC | 3,586 ms
92,924 KB |
testcase_30 | AC | 3,921 ms
97,600 KB |
testcase_31 | AC | 3,826 ms
96,320 KB |
testcase_32 | AC | 3,892 ms
96,960 KB |
testcase_33 | AC | 2,917 ms
95,660 KB |
testcase_34 | AC | 3,294 ms
91,988 KB |
testcase_35 | AC | 3,654 ms
95,608 KB |
testcase_36 | AC | 3,093 ms
94,672 KB |
testcase_37 | AC | 3,391 ms
94,676 KB |
testcase_38 | AC | 2,799 ms
92,820 KB |
testcase_39 | AC | 2,970 ms
95,820 KB |
testcase_40 | AC | 3,511 ms
95,304 KB |
testcase_41 | AC | 77 ms
71,496 KB |
testcase_42 | AC | 79 ms
71,256 KB |
ソースコード
import heapq class MinCostFlow: def __init__(self, n): self.n=n self.g=[[] for _ in range(n)] self.h=[0]*n 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 mincostflow(self, s, t, f): res=0 n=self.n g=self.g h=self.h INF=10**18 h=[0]*n prevv=[0]*n preve=[0]*n while f>0: que=[] dist=[INF]*n dist[s]=0 heapq.heappush(que, s) while len(que)>0: p=heapq.heappop(que) v=(p&((1<<13)-1)) if dist[v]<(p>>13): continue for i, e in enumerate(g[v]): to, cost=e[0], e[2] if e[1]>0 and 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]<<13)^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=int(input()) s=input() v=list(map(int, input().split())) start, end, S, T=n+1, n, n+2, n+3 mcf=MinCostFlow(n+4) mcf.add_edge(S, start, n//4, 0) mcf.add_edge(end, T, n//4, 0) ans=0 f=0 s0="yuki" idx=[n+1]*5 idx[4]=n for i in range(n-1, -1, -1): k=s0.find(s[i]) if idx[k]<=n: mcf.add_edge(i, idx[k], n//4, 0) if idx[k+1]<=n: mcf.add_edge(S, idx[k+1], 1, 0) mcf.add_edge(idx[k+1], i, 1, v[i]) mcf.add_edge(i, T, 1, 0) ans+=v[i] f+=1 idx[k]=i if idx[0]<=n: mcf.add_edge(start, idx[0], n//4, 0) mcf.add_edge(start, end, n//4, 0) ans-=mcf.mincostflow(S, T, n//4+f) print(ans)