結果
問題 |
No.973 余興
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:17:30 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,350 bytes |
コンパイル時間 | 348 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 290,264 KB |
最終ジャッジ日時 | 2025-06-12 13:19:58 |
合計ジャッジ時間 | 11,062 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | TLE * 1 -- * 53 |
ソースコード
def main(): import sys input = sys.stdin.read().split() idx = 0 n = int(input[idx]) idx += 1 X = int(input[idx]) idx += 1 a = list(map(int, input[idx:idx+n])) # Precompute cumulative sums from left and right S_left = [0] * (n + 1) for i in range(n): S_left[i+1] = S_left[i] + a[i] S_right = [0] * (n + 1) for i in range(n-1, -1, -1): S_right[i] = S_right[i+1] + a[i] # Initialize DP table dp = [[False] * n for _ in range(n)] # Function to find maximum k from left def find_max_k_left(l, r): left = 1 right = r - l + 1 max_k = 0 while left <= right: mid = (left + right) // 2 if l + mid > n: right = mid - 1 continue current_sum = S_left[l + mid] - S_left[l] if current_sum <= X: max_k = mid left = mid + 1 else: right = mid - 1 return max_k # Function to find maximum k from right def find_max_k_right(l, r): left = 1 right = r - l + 1 max_k = 0 while left <= right: mid = (left + right) // 2 if (r - mid + 1) < 0: right = mid - 1 continue current_sum = S_right[r - mid + 1] - S_right[r + 1] if current_sum <= X: max_k = mid left = mid + 1 else: right = mid - 1 return max_k # Fill DP table by interval length for length in range(n): for l in range(n - length): r = l + length # Check left max_k_left = find_max_k_left(l, r) if max_k_left > 0: new_l = l + max_k_left new_r = r if new_l <= new_r: if not dp[new_l][new_r]: dp[l][r] = True # Check right max_k_right = find_max_k_right(l, r) if max_k_right > 0: new_l = l new_r = r - max_k_right if new_l <= new_r: if not dp[new_l][new_r]: dp[l][r] = True print("A" if dp[0][n-1] else "B") if __name__ == "__main__": main()