結果

問題 No.119 旅行のツアーの問題
ユーザー cologne
提出日時 2022-02-05 22:28:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,260 ms / 5,000 ms
コード長 2,019 bytes
コンパイル時間 409 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 92,928 KB
最終ジャッジ日時 2024-06-11 13:41:06
合計ジャッジ時間 7,998 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    N = int(input())
    BC = [tuple(map(int, input().split())) for i in range(N)]
    M = int(input())
    DE = [tuple(map(int, input().split())) for i in range(M)]

    first_N = N // 2
    second_N = N - first_N

    first_cost = BC[:first_N]
    second_cost = BC[first_N:]

    first_adj = [0 for i in range(first_N)]
    second_adj = [0 for i in range(second_N)]
    center_adj = [0 for i in range(first_N)]

    for d, e in DE:
        if d < first_N and e < first_N:
            first_adj[d] |= 1 << e
        elif d >= first_N and e >= first_N:
            second_adj[e-first_N] |= 1 << (d-first_N)
        else:
            center_adj[d] |= 1 << (e - first_N)

    # bitmask of tour going
    first_values = [0] * (1 << first_N)
    for i in range(1 << first_N):
        forced_tour = 0
        for j in range(first_N):
            if i & (1 << j):
                forced_tour |= first_adj[j]
                first_values[i] += first_cost[j][0]
            elif not (forced_tour & (1 << j)):
                first_values[i] += first_cost[j][1]

    # bitmask of not tour going
    second_values = [0] * (1 << second_N)
    for i in range(1 << second_N):
        forced_notour = 0
        for j in range(second_N-1, -1, -1):
            if i & (1 << j):
                forced_notour |= second_adj[j]
                second_values[i] += second_cost[j][1]
            elif not (forced_notour & (1 << j)):
                second_values[i] += second_cost[j][0]

    # SOS propagate
    for j in range(second_N):
        for i in range(1 << second_N):
            second_values[i | (1 << j)] = \
                max(second_values[i | (1 << j)], second_values[i])

    ans = 0
    for i in range(1 << first_N):
        forced_tour = 0
        for j in range(first_N):
            if i & (1 << j):
                forced_tour |= center_adj[j]

        ans = max(ans, first_values[i] +
                  second_values[(1 << second_N)-1-forced_tour])

    print(ans)


if __name__ == '__main__':
    main()
0