結果

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

ソースコード

diff # 

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