結果
問題 |
No.1246 ANDORゲーム(max)
|
ユーザー |
👑 ![]() |
提出日時 | 2020-10-03 00:54:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 996 ms / 2,000 ms |
コード長 | 1,175 bytes |
コンパイル時間 | 218 ms |
コンパイル使用メモリ | 82,332 KB |
実行使用メモリ | 90,144 KB |
最終ジャッジ日時 | 2024-07-18 01:46:03 |
合計ジャッジ時間 | 15,387 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
""" https://yukicoder.me/problems/no/1246 andで増えるのは X & A 1 & 0 → 0 で+1 のみ orで増えるのは 0 | 1 → 1 で+1 のみ それ以外は、寄与はしない ====答えを見た==== X & A in X | A である。 X,Yがあって X in Yとする X & A in Y & A X | A in Y | A X & A in Y | A は自明… 左では1だが、右では0がないことを証明する? XYAの全通りで X|A / Y&A を考える 000 → 0/0 001 → 0/0 010 → 1/0 011 → 1/1 110 → 1/0 111 → 1/1 なので、 Y&A in X|A になる 包含関係の2個から生成される対は包含関係になる """ from sys import stdin N,T = map(int,stdin.readline().split()) A = list(map(int,stdin.readline().split())) dp = {} dp[T] = 0 for i in range(N): ndp = {} for j in dp: nex = j & A[i] if nex not in ndp: ndp[nex] = float("-inf") ndp[nex] = max( ndp[nex] , dp[j] + abs(nex-j) ) nex = j | A[i] if nex not in ndp: ndp[nex] = float("-inf") ndp[nex] = max( ndp[nex] , dp[j] + abs(nex-j) ) dp = ndp ans = float("-inf") for i in dp: ans = max(ans ,dp[i]) print (ans)