結果

問題 No.1904 Never giving up!
ユーザー nephrologistnephrologist
提出日時 2022-04-15 22:10:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 838 bytes
コンパイル時間 541 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 269,024 KB
最終ジャッジ日時 2024-06-07 03:16:22
合計ジャッジ時間 8,111 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
55,040 KB
testcase_01 WA -
testcase_02 AC 961 ms
242,264 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 TLE -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

input = sys.stdin.buffer.readline

sys.setrecursionlimit(4100000)
n = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)


@lru_cache(None)
def calc(bit):
    # print("bit", bit)
    if bit == (1 << n) - 1:
        return 1
    res = 0
    mx = -1
    for i in range(n):
        if (bit >> i) & 1:
            mx = max(mx, A[i])
    ok = 0
    ng = 0
    for i in range(n):
        if (bit >> i) & 1:
            continue
        if A[i] >= mx:
            ok += 1
        else:
            ng += 1
    assert ok + ng > 0
    # ratio = 1 / (ok + ng)
    for i in range(n):
        if (bit >> i) & 1:
            continue
        nbit = bit | (1 << i)
        if A[i] >= mx:
            res += (ok + ng) * (calc(nbit))
    return res


cnt = 100
ok = 1
ng = 0
print(calc(0))
0