結果

問題 No.973 余興
ユーザー lam6er
提出日時 2025-04-15 23:07:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,007 bytes
コンパイル時間 456 ms
コンパイル使用メモリ 81,640 KB
実行使用メモリ 289,724 KB
最終ジャッジ日時 2025-04-15 23:10:13
合計ジャッジ時間 10,745 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    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]
    suffix = [0] * (N + 1)
    for i in range(N-1, -1, -1):
        suffix[i] = suffix[i+1] + a[i]
    
    dp = [[False] * N for _ in range(N)]
    
    for length in range(1, N+1):
        for l in range(N - length + 1):
            r = l + length - 1
            left_possible = False
            # Left direction
            low, high = 1, length
            max_left = 0
            while low <= high:
                mid = (low + high) // 2
                if prefix[l + mid] - prefix[l] <= X:
                    max_left = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if max_left > 0:
                for k in range(1, max_left + 1):
                    new_l = l + k
                    if new_l > r:
                        continue
                    if not dp[new_l][r]:
                        left_possible = True
                        break
            # Right direction
            right_possible = False
            low, high = 1, length
            max_right = 0
            while low <= high:
                mid = (low + high) // 2
                s = suffix[r - mid + 1] - suffix[r + 1]
                if s <= X:
                    max_right = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if max_right > 0:
                for k in range(1, max_right + 1):
                    new_r = r - k
                    if l > new_r:
                        continue
                    if not dp[l][new_r]:
                        right_possible = True
                        break
            dp[l][r] = left_possible or right_possible
    print("A" if dp[0][N-1] else "B")

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