結果

問題 No.1904 Never giving up!
コンテスト
ユーザー nephrologist
提出日時 2022-04-15 22:10:53
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 838 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 282 ms
コンパイル使用メモリ 86,016 KB
実行使用メモリ 264,864 KB
最終ジャッジ日時 2026-05-30 17:58:47
合計ジャッジ時間 5,429 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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