結果

問題 No.119 旅行のツアーの問題
ユーザー colognecologne
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
73,856 KB
testcase_01 AC 495 ms
84,352 KB
testcase_02 AC 36 ms
52,224 KB
testcase_03 AC 34 ms
51,840 KB
testcase_04 AC 34 ms
52,480 KB
testcase_05 AC 96 ms
76,800 KB
testcase_06 AC 765 ms
88,576 KB
testcase_07 AC 41 ms
51,840 KB
testcase_08 AC 35 ms
51,968 KB
testcase_09 AC 39 ms
52,224 KB
testcase_10 AC 36 ms
52,224 KB
testcase_11 AC 37 ms
52,352 KB
testcase_12 AC 37 ms
52,224 KB
testcase_13 AC 42 ms
52,736 KB
testcase_14 AC 1,260 ms
92,544 KB
testcase_15 AC 69 ms
70,400 KB
testcase_16 AC 1,259 ms
92,928 KB
testcase_17 AC 36 ms
52,352 KB
testcase_18 AC 37 ms
53,120 KB
testcase_19 AC 67 ms
70,656 KB
testcase_20 AC 175 ms
78,336 KB
testcase_21 AC 764 ms
88,704 KB
testcase_22 AC 1,216 ms
92,928 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