結果
問題 | No.2071 Shift and OR |
ユーザー |
![]() |
提出日時 | 2022-11-05 11:40:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 153 ms / 2,000 ms |
コード長 | 961 bytes |
コンパイル時間 | 153 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 104,868 KB |
最終ジャッジ日時 | 2024-07-19 06:10:31 |
合計ジャッジ時間 | 5,285 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
from typing import List, Tuple, Optional import sys import itertools import heapq import bisect from collections import deque, defaultdict from functools import lru_cache, cmp_to_key input = sys.stdin.readline # for AtCoder Easy test if __file__ != 'prog.py': sys.setrecursionlimit(10 ** 6) def readints(): return map(int, input().split()) def readlist(): return list(readints()) def readstr(): return input().rstrip() N = int(input()) A = readlist() if N > 15: print((1 << 16) - 1) exit() dp = [False] * (1 << 16) dp[0] = True for a in A: ndp = [False] * (1 << 16) for j in range(1 << 16): if dp[j] is False: continue acc = a for k in range(16): ndp[j | acc] = True if acc & 1: acc = (acc >> 1) + (1 << 15) else: acc = (acc >> 1) dp = ndp for s in range(1 << 16)[::-1]: if dp[s] is True: print(s) break