結果
問題 |
No.973 余興
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:13:06 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,286 bytes |
コンパイル時間 | 381 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 280,640 KB |
最終ジャッジ日時 | 2025-04-16 16:17:53 |
合計ジャッジ時間 | 10,863 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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())) n = N # Precompute prefix sums for left and right left_sum = [0] * (n + 1) for i in range(n): left_sum[i+1] = left_sum[i] + a[i] right_sum = [0] * (n + 2) for i in range(n, 0, -1): right_sum[i] = right_sum[i+1] + a[i-1] dp = [[False] * n for _ in range(n)] for length in range(1, n+1): for l in range(n - length + 1): r = l + length - 1 # Check left side maximum k max_k = 0 low, high = 1, length while low <= high: mid = (low + high) // 2 end = l + mid if end > n: high = mid - 1 continue s = left_sum[end] - left_sum[l] if s <= X: max_k = mid low = mid + 1 else: high = mid - 1 win_left = False if max_k > 0: new_l = l + max_k new_r = r if new_l > new_r: # Taking all, current player loses win_left = False else: win_left = not dp[new_l][new_r] # Check right side maximum m max_m = 0 low, high = 1, length while low <= high: mid = (low + high) // 2 start = r - mid + 1 if start < 1: high = mid - 1 continue s = right_sum[start] - right_sum[r+1] if s <= X: max_m = mid low = mid + 1 else: high = mid - 1 win_right = False if max_m > 0: new_l = l new_r = r - max_m if new_l > new_r: # Taking all, current player loses win_right = False else: win_right = not dp[new_l][new_r] dp[l][r] = win_left or win_right print("A" if dp[0][n-1] else "B") if __name__ == '__main__': main()