結果
問題 |
No.973 余興
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:17:43 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,172 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 81,616 KB |
実行使用メモリ | 485,596 KB |
最終ジャッジ日時 | 2025-04-15 23:19:13 |
合計ジャッジ時間 | 10,816 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | TLE * 1 -- * 53 |
ソースコード
import sys def main(): N, X = map(int, sys.stdin.readline().split()) a = list(map(int, sys.stdin.readline().split())) a = [0] + a # 1-based index # Precompute prefix sums for left and right S_left = [0] * (N + 1) for i in range(1, N+1): S_left[i] = S_left[i-1] + a[i] S_right = [0] * (N + 2) # S_right[i] is sum from a[i] to a[N] for i in range(N, 0, -1): S_right[i] = S_right[i+1] + a[i] # DP_A[l][r]: A's turn, can win? DP_A = [[False]*(N+2) for _ in range(N+2)] DP_B = [[False]*(N+2) for _ in range(N+2)] for len_ in range(0, N+1): for l in range(1, N+1): r = l + len_ - 1 if r > N: continue if l > r: # No creampuffs left, current player wins DP_A[l][r] = True DP_B[l][r] = True continue # Compute for A's turn can_win_A = False # Check left max_left = 0 low, high = 1, len_ while low <= high: mid = (low + high) // 2 if l + mid - 1 > N: high = mid - 1 continue s = S_left[l + mid - 1] - S_left[l-1] if s <= X: max_left = mid low = mid + 1 else: high = mid - 1 if max_left >= 1: # Check k=1 and k=max_left for k in [1, max_left]: if k > max_left: continue new_l = l + k new_r = r if new_l > new_r: # A takes all, loses continue if not DP_B[new_l][new_r]: can_win_A = True break if not can_win_A: # Check right max_right = 0 low, high = 1, len_ while low <= high: mid = (low + high) // 2 start = r - mid + 1 if start < 1: high = mid - 1 continue s = S_right[start] - S_right[r+1] if s <= X: max_right = mid low = mid + 1 else: high = mid - 1 if max_right >= 1: for k in [1, max_right]: if k > max_right: continue new_l = l new_r = r - k if new_l > new_r: # A takes all, loses continue if not DP_B[new_l][new_r]: can_win_A = True break DP_A[l][r] = can_win_A # Compute for B's turn can_win_B = False # Check left max_left = 0 low, high = 1, len_ while low <= high: mid = (low + high) // 2 if l + mid - 1 > N: high = mid - 1 continue s = S_left[l + mid - 1] - S_left[l-1] if s <= X: max_left = mid low = mid + 1 else: high = mid - 1 if max_left >= 1: for k in [1, max_left]: if k > max_left: continue new_l = l + k new_r = r if new_l > new_r: # B takes all, loses continue if not DP_A[new_l][new_r]: can_win_B = True break if not can_win_B: # Check right max_right = 0 low, high = 1, len_ while low <= high: mid = (low + high) // 2 start = r - mid + 1 if start < 1: high = mid - 1 continue s = S_right[start] - S_right[r+1] if s <= X: max_right = mid low = mid + 1 else: high = mid - 1 if max_right >= 1: for k in [1, max_right]: if k > max_right: continue new_l = l new_r = r - k if new_l > new_r: # B takes all, loses continue if not DP_A[new_l][new_r]: can_win_B = True break DP_B[l][r] = can_win_B if DP_A[1][N]: print("A") else: print("B") if __name__ == "__main__": main()