結果

問題 No.973 余興
コンテスト
ユーザー lam6er
提出日時 2025-03-31 18:00:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,029 bytes
コンパイル時間 379 ms
コンパイル使用メモリ 82,300 KB
実行使用メモリ 483,768 KB
最終ジャッジ日時 2025-03-31 18:01:07
合計ジャッジ時間 10,807 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import bisect
    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]

    dp_a = [[False] * n for _ in range(n)]
    dp_b = [[False] * n for _ in range(n)]

    for length in range(1, n + 1):
        for l in range(n - length + 1):
            r = l + length - 1

            max_left = 0
            low, high = 1, length
            while low <= high:
                mid = (low + high) // 2
                if prefix[l + mid] - prefix[l] <= X:
                    max_left = mid
                    low = mid + 1
                else:
                    high = mid - 1

            can_win_a = False
            if max_left > 0:
                for k in range(1, max_left + 1):
                    new_l = l + k
                    new_r = r
                    if new_l > new_r:
                        continue
                    if not dp_b[new_l][new_r]:
                        can_win_a = True
                        break
                if can_win_a:
                    dp_a[l][r] = True
                    continue

            max_right = 0
            low, high = 1, length
            while low <= high:
                mid = (low + high) // 2
                start = r - mid + 1
                if start < l:
                    high = mid - 1
                    continue
                if prefix[r + 1] - prefix[start] <= X:
                    max_right = mid
                    low = mid + 1
                else:
                    high = mid - 1

            if max_right > 0:
                for k in range(1, max_right + 1):
                    new_l = l
                    new_r = r - k
                    if new_l > new_r:
                        continue
                    if not dp_b[new_l][new_r]:
                        can_win_a = True
                        break
            dp_a[l][r] = can_win_a

            max_left_b = max_left
            max_right_b = max_right

            can_win_b = False
            if max_left_b > 0:
                for k in range(1, max_left_b + 1):
                    new_l = l + k
                    new_r = r
                    if new_l > new_r:
                        continue
                    if not dp_a[new_l][new_r]:
                        can_win_b = True
                        break
                if can_win_b:
                    dp_b[l][r] = True
                    continue

            if max_right_b > 0:
                for k in range(1, max_right_b + 1):
                    new_l = l
                    new_r = r - k
                    if new_l > new_r:
                        continue
                    if not dp_a[new_l][new_r]:
                        can_win_b = True
                        break
            dp_b[l][r] = can_win_b

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

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