結果
問題 |
No.1825 Except One
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:34:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,237 ms / 3,000 ms |
コード長 | 1,001 bytes |
コンパイル時間 | 385 ms |
コンパイル使用メモリ | 81,536 KB |
実行使用メモリ | 195,968 KB |
最終ジャッジ日時 | 2025-06-12 21:36:22 |
合計ジャッジ時間 | 8,300 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
import sys from collections import defaultdict def main(): N, *rest = list(map(int, sys.stdin.read().split())) A = rest[:N] max_m = N DP = [defaultdict(int) for _ in range(max_m + 1)] DP[0][(0, 0)] = 1 for a in A: for m in range(max_m, -1, -1): if m > N: continue current = DP[m] for (s, mx), cnt in list(current.items()): new_m = m + 1 if new_m > max_m: continue new_s = s + a new_mx = max(mx, a) DP[new_m][(new_s, new_mx)] += cnt ans = 0 for m in range(2, max_m + 1): current = DP[m] for (s, mx), cnt in current.items(): if (m - 1) == 0: continue if s % (m - 1) != 0: continue S = s // (m - 1) if mx > S: continue ans += cnt print(ans) if __name__ == "__main__": main()