結果
問題 |
No.1825 Except One
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:50:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,186 ms / 3,000 ms |
コード長 | 1,156 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 200,556 KB |
最終ジャッジ日時 | 2025-06-12 16:51:35 |
合計ジャッジ時間 | 7,272 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
import sys from collections import defaultdict def main(): N, *rest = map(int, sys.stdin.read().split()) A = rest[:N] # Initialize DP: dp[m] is a dictionary where keys are (sum, max) and values are counts dp = [defaultdict(int) for _ in range(N+1)] dp[0][(0, 0)] = 1 # Base case: empty subsequence for a in A: # Iterate m in reverse to avoid using the same a multiple times in the same step for m in range(N-1, -1, -1): # Make a copy of the current state to iterate over current = list(dp[m].items()) for (s, x), cnt in current: new_m = m + 1 new_s = s + a new_x = max(x, a) if new_m > N: continue dp[new_m][(new_s, new_x)] += cnt ans = 0 for m in range(2, N+1): divisor = m - 1 if divisor == 0: continue for (s, x), cnt in dp[m].items(): if s % divisor != 0: continue k = s // divisor if x <= k: ans += cnt print(ans) if __name__ == "__main__": main()