結果

問題 No.973 余興
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:17:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,350 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 290,264 KB
最終ジャッジ日時 2025-06-12 13:19:58
合計ジャッジ時間 11,062 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    X = int(input[idx])
    idx += 1
    a = list(map(int, input[idx:idx+n]))
    
    # Precompute cumulative sums from left and right
    S_left = [0] * (n + 1)
    for i in range(n):
        S_left[i+1] = S_left[i] + a[i]
    
    S_right = [0] * (n + 1)
    for i in range(n-1, -1, -1):
        S_right[i] = S_right[i+1] + a[i]
    
    # Initialize DP table
    dp = [[False] * n for _ in range(n)]
    
    # Function to find maximum k from left
    def find_max_k_left(l, r):
        left = 1
        right = r - l + 1
        max_k = 0
        while left <= right:
            mid = (left + right) // 2
            if l + mid > n:
                right = mid - 1
                continue
            current_sum = S_left[l + mid] - S_left[l]
            if current_sum <= X:
                max_k = mid
                left = mid + 1
            else:
                right = mid - 1
        return max_k
    
    # Function to find maximum k from right
    def find_max_k_right(l, r):
        left = 1
        right = r - l + 1
        max_k = 0
        while left <= right:
            mid = (left + right) // 2
            if (r - mid + 1) < 0:
                right = mid - 1
                continue
            current_sum = S_right[r - mid + 1] - S_right[r + 1]
            if current_sum <= X:
                max_k = mid
                left = mid + 1
            else:
                right = mid - 1
        return max_k
    
    # Fill DP table by interval length
    for length in range(n):
        for l in range(n - length):
            r = l + length
            # Check left
            max_k_left = find_max_k_left(l, r)
            if max_k_left > 0:
                new_l = l + max_k_left
                new_r = r
                if new_l <= new_r:
                    if not dp[new_l][new_r]:
                        dp[l][r] = True
            # Check right
            max_k_right = find_max_k_right(l, r)
            if max_k_right > 0:
                new_l = l
                new_r = r - max_k_right
                if new_l <= new_r:
                    if not dp[new_l][new_r]:
                        dp[l][r] = True
    
    print("A" if dp[0][n-1] else "B")

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