結果

問題 No.973 余興
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:53:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,408 bytes
コンパイル時間 340 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 286,336 KB
最終ジャッジ日時 2025-06-12 20:57:45
合計ジャッジ時間 10,744 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()))
    
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i-1] + a[i-1]
    
    dp = [[False] * (n + 2) for _ in range(n + 2)]
    
    for length in range(1, n + 1):
        for l in range(1, n - length + 2):
            r = l + length - 1
            
            # 计算左边的最大k
            max_left = 0
            low, high = 1, r - l + 1
            while low <= high:
                mid = (low + high) // 2
                end = l + mid - 1
                if end > r:
                    high = mid - 1
                    continue
                s = prefix[end] - prefix[l-1]
                if s <= x:
                    max_left = mid
                    low = mid + 1
                else:
                    high = mid - 1
            
            # 计算右边的最大k
            max_right = 0
            low, high = 1, r - l + 1
            while low <= high:
                mid = (low + high) // 2
                start = r - mid + 1
                if start < l:
                    high = mid - 1
                    continue
                s = prefix[r] - prefix[start - 1]
                if s <= x:
                    max_right = mid
                    low = mid + 1
                else:
                    high = mid - 1
            
            found = False
            
            # 检查左边分割
            for k in range(1, max_left + 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
            
            # 检查右边分割
            for k in range(1, max_right + 1):
                new_l = l
                new_r = r - k
                if new_r < new_l:
                    continue  # 分割后的区间为空，不能选
                if not dp[new_l][new_r]:
                    found = True
                    break
            
            dp[l][r] = found
    
    if dp[1][n]:
        print("A")
    else:
        print("B")

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