結果

問題 No.973 余興
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0