結果

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

ソースコード

diff # 

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    n, X = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + a[i]
    
    # Precompute k_left and k_right
    k_left = [0] * n
    for i in range(n):
        low = 1
        high = n - i
        best = 0
        while low <= high:
            mid = (low + high) // 2
            end = i + mid
            if end > n:
                high = mid - 1
                continue
            s = prefix[end] - prefix[i]
            if s <= X:
                best = mid
                low = mid + 1
            else:
                high = mid - 1
        k_left[i] = best
    
    k_right = [0] * n
    for j in range(n):
        low = 1
        high = j + 1
        best = 0
        while low <= high:
            mid = (low + high) // 2
            start = j + 1 - mid
            if start < 0:
                high = mid - 1
                continue
            s = prefix[j+1] - prefix[start]
            if s <= X:
                best = mid
                low = mid + 1
            else:
                high = mid - 1
        k_right[j] = best
    
    # Initialize dp
    dp = [[False] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = (prefix[i+1] - prefix[i] > X)
    
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            sum_total = prefix[j+1] - prefix[i]
            if sum_total <= X:
                dp[i][j] = False
                continue
            
            found = False
            
            # Check left
            max_k_left = min(k_left[i], length)
            if max_k_left > 0:
                for k in range(1, max_k_left + 1):
                    if i + k > j:
                        break
                    remaining_i = i + k
                    remaining_j = j
                    if remaining_i > remaining_j:
                        found = True
                        break
                    remaining_sum = prefix[remaining_j + 1] - prefix[remaining_i]
                    if remaining_sum <= X:
                        found = True
                        break
                if found:
                    dp[i][j] = True
                    continue
            
            # Check right
            max_k_right = min(k_right[j], length)
            if max_k_right > 0:
                for k in range(1, max_k_right + 1):
                    if j - k + 1 < i:
                        break
                    remaining_i = i
                    remaining_j = j - k
                    if remaining_i > remaining_j:
                        found = True
                        break
                    remaining_sum = prefix[remaining_j + 1] - prefix[remaining_i]
                    if remaining_sum <= X:
                        found = True
                        break
                if found:
                    dp[i][j] = True
                    continue
            
            # Second phase
            found = False
            max_k_left = min(k_left[i], length)
            if max_k_left > 0:
                for k in range(1, max_k_left + 1):
                    if i + k > j:
                        break
                    remaining_i = i + k
                    remaining_j = j
                    if remaining_i > remaining_j:
                        found = True
                        break
                    else:
                        if not dp[remaining_i][remaining_j]:
                            found = True
                            break
                if found:
                    dp[i][j] = True
                    continue
            
            max_k_right = min(k_right[j], length)
            if max_k_right > 0:
                for k in range(1, max_k_right + 1):
                    if j - k + 1 < i:
                        break
                    remaining_i = i
                    remaining_j = j - k
                    if remaining_i > remaining_j:
                        found = True
                        break
                    else:
                        if not dp[remaining_i][remaining_j]:
                            found = True
                            break
                if found:
                    dp[i][j] = True
                    continue
            
            dp[i][j] = False
    
    if dp[0][n-1]:
        print("A")
    else:
        print("B")

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