結果
問題 | No.1288 yuki collection |
ユーザー |
|
提出日時 | 2024-10-12 15:16:01 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,342 bytes |
コンパイル時間 | 991 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 65,152 KB |
最終ジャッジ日時 | 2024-10-12 15:16:07 |
合計ジャッジ時間 | 3,939 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | RE * 40 |
ソースコード
## https://yukicoder.me/problems/no/1288from atcoder.mincostflow import MCFGraphMAXINT = 10 ** 14def main():N = int(input())S = input()V = list(map(int, input().split()))# ネットワークフローを使って解くmcf_graph = MCFGraph(2 * N + 2)for i in range(N):if S[i] == "y":mcf_graph.add_edge(0, i + 1, 1, 0)for i in range(N):if S[i] == "u":for j in range(i):if S[j] == "y":mcf_graph.add_edge(N + j + 1, i + 1, 1, 0)elif S[i] == "k":for j in range(i):if S[j] == "u":mcf_graph.add_edge(N + j + 1, i + 1, 1, 0)elif S[i] == "i":for j in range(i):if S[j] == "k":mcf_graph.add_edge(N + j + 1, i + 1, 1, 0)for i in range(N):if S[i] == "i":mcf_graph.add_edge(N + i + 1, 2 * N + 1, 1, 0)for i in range(N):mcf_graph.add_edge(i + 1, N + i + 1, 1, MAXINT - V[i])s_list = mcf_graph.slope(0, 2 * N + 1)answer = 0for f, a in s_list:x = f * 4 * MAXINT - aanswer = max(answer, x)print(answer)if __name__ == "__main__":main()