結果

問題 No.1904 Never giving up!
コンテスト
ユーザー nephrologist
提出日時 2022-04-15 22:10:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 838 bytes
コンパイル時間 435 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 502,668 KB
最終ジャッジ日時 2024-12-25 00:50:25
合計ジャッジ時間 9,327 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other WA * 7 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

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