結果
問題 |
No.973 余興
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:48:54 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,593 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 82,660 KB |
実行使用メモリ | 288,744 KB |
最終ジャッジ日時 | 2025-03-20 20:49:14 |
合計ジャッジ時間 | 10,806 ms |
ジャッジサーバーID (参考情報) |
judge5 / 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())) # Precompute prefix sums for the array sum_left = [0] * (n + 1) for i in range(n): sum_left[i + 1] = sum_left[i] + a[i] # Initialize DP table: dp[l][r] indicates if the current player can win starting from interval [l, r] dp = [[False] * n for _ in range(n)] # Process intervals in increasing order of length for length in range(1, n + 1): for l in range(n - length + 1): r = l + length - 1 # Check all possible moves from the left max_k = 0 low, high = 1, length while low <= high: mid = (low + high) // 2 if l + mid > n: high = mid - 1 continue current_sum = sum_left[l + mid] - sum_left[l] if current_sum <= X: max_k = mid low = mid + 1 else: high = mid - 1 found = False for k in range(1, max_k + 1): new_l = l + k new_r = r if new_l > new_r: continue if not dp[new_l][new_r]: found = True break if found: dp[l][r] = True continue # Check all possible moves from the right max_m = 0 low, high = 1, length while low <= high: mid = (low + high) // 2 start = r - mid + 1 if start < 0: high = mid - 1 continue current_sum = sum_left[r + 1] - sum_left[start] if current_sum <= X: max_m = mid low = mid + 1 else: high = mid - 1 found = False for m in range(1, max_m + 1): new_l = l new_r = r - m if new_l > new_r: continue if not dp[new_l][new_r]: found = True break if found: dp[l][r] = True else: dp[l][r] = False # Determine the result for the initial state if dp[0][n - 1]: print("A") else: print("B") if __name__ == "__main__": main()