結果

問題 No.119 旅行のツアーの問題
ユーザー 👑 colognecologne
提出日時 2022-02-05 22:28:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,442 ms / 5,000 ms
コード長 2,019 bytes
コンパイル時間 269 ms
コンパイル使用メモリ 87,244 KB
実行使用メモリ 94,284 KB
最終ジャッジ日時 2023-09-02 06:52:36
合計ジャッジ時間 10,159 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 100 ms
77,264 KB
testcase_01 AC 565 ms
85,528 KB
testcase_02 AC 70 ms
71,576 KB
testcase_03 AC 70 ms
71,412 KB
testcase_04 AC 70 ms
71,364 KB
testcase_05 AC 122 ms
77,792 KB
testcase_06 AC 872 ms
89,936 KB
testcase_07 AC 68 ms
71,476 KB
testcase_08 AC 69 ms
71,084 KB
testcase_09 AC 70 ms
71,320 KB
testcase_10 AC 68 ms
71,368 KB
testcase_11 AC 70 ms
71,296 KB
testcase_12 AC 69 ms
71,532 KB
testcase_13 AC 70 ms
71,400 KB
testcase_14 AC 1,442 ms
93,884 KB
testcase_15 AC 94 ms
77,320 KB
testcase_16 AC 1,388 ms
94,284 KB
testcase_17 AC 70 ms
71,344 KB
testcase_18 AC 70 ms
71,312 KB
testcase_19 AC 96 ms
77,196 KB
testcase_20 AC 211 ms
79,784 KB
testcase_21 AC 855 ms
89,724 KB
testcase_22 AC 1,386 ms
94,212 KB
権限があれば一括ダウンロードができます

ソースコード

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