結果

問題 No.3594 Subset OR
ユーザー lif4635
提出日時 2026-07-21 19:33:42
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 1,792 ms / 3,000 ms
+ 806µs
コード長 752 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 294 ms
コンパイル使用メモリ 21,536 KB
実行使用メモリ 191,540 KB
最終ジャッジ日時 2026-07-23 20:36:12
合計ジャッジ時間 65,693 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

lo = 12
hi = 30 - lo

s = 1 << lo
mask = s - 1

bucket = [[] for _ in range(s)]
for x in a:
    bucket[x & mask].append(x >> lo)

dp = [0] * s
hs = 1 << hi
buf = bytearray(hs >> 3)
for i in range(s):
    for x in bucket[i]:
        buf[x >> 3] |= 1 << (x & 7)
    dp[i] = int.from_bytes(buf, "little")
    for x in bucket[i]:
        buf[x >> 3] = 0

for b in range(lo):
    bit = 1 << b
    x = bit
    while x < s:
        dp[x ^ bit] |= dp[x]
        x = (x + 1) | bit

full = (1 << hs) - 1
f = []
for b in range(hi):
    bit = 1 << b
    f.append((full // ((1 << bit) + 1)) << bit)

ans = 0
for x in dp:
    for b in range(hi):
        x |= (x & f[b]) >> (1 << b)
    ans += x.bit_count()

print(ans)
0