結果

問題 No.1825 Except One
ユーザー gew1fw
提出日時 2025-06-12 18:48:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 191 ms / 3,000 ms
コード長 1,209 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 81,784 KB
実行使用メモリ 85,176 KB
最終ジャッジ日時 2025-06-12 18:49:08
合計ジャッジ時間 3,981 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
a.sort()

# Initialize DP: dp[size][sum] = count
dp = defaultdict(lambda: defaultdict(int))
dp[0][0] = 1

ans = 0

for i in range(n):
    current = a[i]
    # Check all possible subset sizes where current is the maximum element
    for m in range(2, i + 2):  # m ranges from 2 to i+1 inclusive
        required_size = m - 1
        if required_size not in dp:
            continue
        sum_dict = dp[required_size]
        for sum_other in sum_dict:
            total_sum = sum_other + current
            if (total_sum) % (m - 1) != 0:
                continue
            K = total_sum // (m - 1)
            if K >= current:
                ans += sum_dict[sum_other]
    # Update DP by adding current to existing subsets
    new_dp = defaultdict(lambda: defaultdict(int))
    # Copy existing entries
    for s in dp:
        for t in dp[s]:
            new_dp[s][t] += dp[s][t]
    # Add new entries by including current in existing subsets
    for s in dp:
        for t in dp[s]:
            new_s = s + 1
            new_t = t + current
            new_dp[new_s][new_t] += dp[s][t]
    dp = new_dp

print(ans)
0