結果

問題 No.973 余興
ユーザー gew1fw
提出日時 2025-06-12 13:23:14
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,270 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 849,276 KB
最終ジャッジ日時 2025-06-12 13:27:48
合計ジャッジ時間 10,358 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other MLE * 1 -- * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    n, X = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    n = len(a)
    
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + a[i]
    
    suffix = [0] * (n + 2)
    for i in range(n-1, -1, -1):
        suffix[i+1] = suffix[i+2] + a[i]
    
    memo = [[[-1 for _ in range(2)] for __ in range(n)] for ___ in range(n)]
    
    def dfs(left, right, turn):
        if left > right:
            return True  # Current player wins as the opponent took the last
        if memo[left][right][turn] != -1:
            return memo[left][right][turn]
        
        can_win = False
        
        # Left side
        low, high = 1, right - left + 1
        max_k = 0
        while low <= high:
            mid = (low + high) // 2
            total = prefix[left + mid] - prefix[left]
            if total <= X:
                max_k = mid
                low = mid + 1
            else:
                high = mid - 1
        if max_k > 0:
            new_left = left + max_k
            res = dfs(new_left, right, 1 - turn)
            if not res:
                can_win = True
        if not can_win and max_k > 0:
            new_left = left + 1
            res = dfs(new_left, right, 1 - turn)
            if not res:
                can_win = True
        
        # Right side
        low, high = 1, right - left + 1
        max_m = 0
        while low <= high:
            mid = (low + high) // 2
            total = suffix[right - mid + 1] - suffix[right + 1]
            if total <= X:
                max_m = mid
                low = mid + 1
            else:
                high = mid - 1
        if max_m > 0 and not can_win:
            new_right = right - max_m
            res = dfs(left, new_right, 1 - turn)
            if not res:
                can_win = True
        if max_m > 0 and not can_win:
            new_right = right - 1
            res = dfs(left, new_right, 1 - turn)
            if not res:
                can_win = True
        
        memo[left][right][turn] = can_win
        return can_win
    
    result = dfs(0, n-1, 0)
    print("A" if result else "B")

if __name__ == "__main__":
    main()
0