結果
問題 | No.1443 Andd |
ユーザー |
|
提出日時 | 2024-10-26 18:31:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,249 ms / 2,000 ms |
コード長 | 957 bytes |
コンパイル時間 | 383 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 77,976 KB |
最終ジャッジ日時 | 2024-10-26 18:32:08 |
合計ジャッジ時間 | 10,969 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
## https://yukicoder.me/problems/no/1443 def main(): N = int(input()) A = list(map(int, input().split())) maxa = max(A) k = 0 while (1 << k) <= maxa: k += 1 dp = [0] * (1 << k) a_set = {0} answer = [0] * N for i in range(N): a = A[i] new_dp = [0] * (1 << k) new_a_set = set() for x in a_set: b = x & a new_a_set.add(b) c = x + a if c < (1 << k): new_a_set.add(c) else: new_dp[c % (1 << k)] += 1 for x in range(1 << k): if dp[x] > 0: b = x & a new_a_set.add(b) c = (x + a) % (1 << k) new_dp[c] += dp[x] a_set = new_a_set dp = new_dp answer[i] = sum(dp) + len(a_set) for i in range(N): print(answer[i]) if __name__ == "__main__": main()