結果

問題 No.973 余興
ユーザー gew1fw
提出日時 2025-06-12 18:31:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,581 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 285,824 KB
最終ジャッジ日時 2025-06-12 18:33:34
合計ジャッジ時間 9,701 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30 WA * 20 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, X = map(int, input().split())
a = list(map(int, input().split()))
n = len(a)

prefix_sum = [0] * (n + 1)
for i in range(n):
    prefix_sum[i + 1] = prefix_sum[i] + a[i]

suffix_sum = [0] * (n + 2)
for i in range(n - 1, -1, -1):
    suffix_sum[i] = suffix_sum[i + 1] + a[i]

dp = [[False] * (n + 2) for _ in range(n + 2)]

for length in range(1, n + 1):
    for l in range(n - length + 1):
        r = l + length - 1
        max_k_left = 0
        low, high = 1, length
        while low <= high:
            mid = (low + high) // 2
            sum_val = prefix_sum[l + mid] - prefix_sum[l]
            if sum_val <= X:
                max_k_left = mid
                low = mid + 1
            else:
                high = mid - 1
        if max_k_left > 0:
            new_l = l + max_k_left
            new_r = r
            if new_l > new_r:
                pass
            else:
                if not dp[new_l][new_r]:
                    dp[l][r] = True
        max_k_right = 0
        low, high = 1, length
        while low <= high:
            mid = (low + high) // 2
            start = r - mid + 1
            sum_val = suffix_sum[start] - suffix_sum[r + 1]
            if sum_val <= X:
                max_k_right = mid
                low = mid + 1
            else:
                high = mid - 1
        if max_k_right > 0:
            new_l = l
            new_r = r - max_k_right
            if new_l > new_r:
                pass
            else:
                if not dp[new_l][new_r]:
                    dp[l][r] = True

print("A" if dp[0][n-1] else "B")
0