結果
問題 |
No.1825 Except One
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:46:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 193 ms / 3,000 ms |
コード長 | 1,209 bytes |
コンパイル時間 | 300 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 85,192 KB |
最終ジャッジ日時 | 2025-06-12 13:46:56 |
合計ジャッジ時間 | 3,742 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
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)