結果
問題 |
No.973 余興
|
ユーザー |
![]() |
提出日時 | 2025-06-12 18:33:00 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,414 bytes |
コンパイル時間 | 212 ms |
コンパイル使用メモリ | 82,180 KB |
実行使用メモリ | 488,240 KB |
最終ジャッジ日時 | 2025-06-12 18:33:11 |
合計ジャッジ時間 | 10,766 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | TLE * 1 -- * 53 |
ソースコード
import bisect n, X = map(int, input().split()) a = list(map(int, input().split())) N = n # Precompute cumulative sums from left and right sum_left = [0] * (N + 1) for i in range(1, N + 1): sum_left[i] = sum_left[i - 1] + a[i - 1] sum_right = [0] * (N + 1) for i in range(1, N + 1): sum_right[i] = sum_right[i - 1] + a[N - i] # Initialize DP tables for A and B dpA = [[False] * (N + 1) for _ in range(N + 1)] dpB = [[False] * (N + 1) for _ in range(N + 1)] # Base case: empty interval, the current player wins for l in range(N + 1): dpA[l][l] = True # A's turn, no puffs left → A wins (last eaten by B) dpB[l][l] = True # B's turn, no puffs left → B wins (last eaten by A) # Fill DP tables for intervals of increasing length for d in range(1, N + 1): for l in range(N - d + 1): r = l + d # Update dpA[l][r] for player A's turn # Check left end target_left = sum_left[l] + X k_left = bisect.bisect_right(sum_left, target_left) - l - 1 k_left = max(0, min(k_left, d)) if k_left > 0: new_l = l + k_left if not dpB[new_l][r]: dpA[l][r] = True if not dpA[l][r]: # Check right end pos = N - r base = sum_right[pos] target_right = base + X k_right = bisect.bisect_right(sum_right, target_right) - pos - 1 k_right = max(0, min(k_right, d)) if k_right > 0: new_r = r - k_right if not dpB[l][new_r]: dpA[l][r] = True # Update dpB[l][r] for player B's turn # Check left end target_left = sum_left[l] + X k_left = bisect.bisect_right(sum_left, target_left) - l - 1 k_left = max(0, min(k_left, d)) if k_left > 0: new_l = l + k_left if not dpA[new_l][r]: dpB[l][r] = True if not dpB[l][r]: # Check right end pos = N - r base = sum_right[pos] target_right = base + X k_right = bisect.bisect_right(sum_right, target_right) - pos - 1 k_right = max(0, min(k_right, d)) if k_right > 0: new_r = r - k_right if not dpA[l][new_r]: dpB[l][r] = True # Determine the winner based on the initial state print("A" if dpA[0][N] else "B")