結果
問題 | No.1267 Stop and Coin Game |
ユーザー |
![]() |
提出日時 | 2020-10-23 23:40:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 967 ms / 2,000 ms |
コード長 | 641 bytes |
コンパイル時間 | 334 ms |
コンパイル使用メモリ | 82,828 KB |
実行使用メモリ | 84,544 KB |
最終ジャッジ日時 | 2024-07-21 13:40:45 |
合計ジャッジ時間 | 10,855 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
N, V = map(int, input().split()) *A, = map(int, input().split()) if sum(A) <= V: print('Draw') exit() dp = [0]*(1<<N) for bit in range((1<<N)-1, -1, -1): tot = 0 cnt = bin(bit).count('1') res = 1 if cnt & 1 else 2 for i in range(N): if bit >> i & 1: tot += A[i] else: nb = bit|(1<<i) if cnt & 1: if dp[nb] == 2: res = 2 else: if dp[nb] == 1: res = 1 if tot > V: dp[bit] = 2 if cnt & 1 else 1 else: dp[bit] = res print('First' if dp[0] == 1 else 'Second')