結果
問題 |
No.973 余興
|
ユーザー |
![]() |
提出日時 | 2025-06-12 16:03:05 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,408 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 281,952 KB |
最終ジャッジ日時 | 2025-06-12 16:03:19 |
合計ジャッジ時間 | 10,848 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | TLE * 1 -- * 53 |
ソースコード
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()