結果

問題 No.3097 Azuki Kurai
コンテスト
ユーザー daikusutora
提出日時 2026-09-28 20:36:20
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,727 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 336 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 313,528 KB
最終ジャッジ日時 2026-09-28 20:36:37
合計ジャッジ時間 15,302 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from atcoder.mincostflow import MCFGraph

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = float("inf")
for m in range(1, M + 1):
    # 0 ~ N*(m+1)-1: 各日にちに対応する頂点の番号
    # N*(m+1) ~ N*(m+1)+N*m-1: 分配器頂点
    # N*(2*m+1): 始点
    # N*(2*m+1)+1: 終点
    graph = MCFGraph(N * (2 * m + 1) + 2)
    # 始点 -> 0日目の家頂点に対して辺を張る
    for i in range(N):
        graph.add_edge(N * (2 * m + 1), i, A[i], 0)
    # j日目~j+1日目に対して辺を張る
    for j in range(m + 1):
        for i in range(N):
            if j > 0:
                if j == m and j - 1 < M and B[j - 1] != i + 1:
                    graph.add_edge(i + j * N, N * (2 * m + 1) + 1, INF, 0)
                if j - 1 < M and B[j - 1] == i + 1:
                    graph.add_edge(i + j * N, N * (2 * m + 1) + 1, INF, 1)
            if j < m:
                # 自分の家に小豆を残す辺 OK
                graph.add_edge(i + j * N, i + (j + 1) * N, INF, 0)
                if j == 0 or (j > 0 and B[j - 1] != i + 1):
                    # 自分の家から分配器への辺 OK
                    graph.add_edge(i + j * N, (i + j * N) + (N * (m + 1)), K, 0)
                    # 分配器から次のj+1日目の左隣の家と右隣の家への辺 OK
                    graph.add_edge(
                        (i + j * N) + (N * (m + 1)), (i - 1) % N + (j + 1) * N, INF, 0
                    )
                    graph.add_edge(
                        (i + j * N) + (N * (m + 1)), (i + 1) % N + (j + 1) * N, INF, 0
                    )
    print(sum(A) - graph.flow(N * (2 * m + 1), N * (2 * m + 1) + 1)[1])
0