結果
問題 |
No.973 余興
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:53:06 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,253 bytes |
コンパイル時間 | 216 ms |
コンパイル使用メモリ | 81,860 KB |
実行使用メモリ | 289,768 KB |
最終ジャッジ日時 | 2025-06-12 20:57:08 |
合計ジャッジ時間 | 10,720 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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())) pre_sum = [0] * (n + 1) for i in range(1, n+1): pre_sum[i] = pre_sum[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 found = False # 处理左边的情况 max_possible_k = r - l +1 low = 1 high = max_possible_k best_k = 0 while low <= high: mid = (low + high) // 2 end = l + mid -1 if end > r: high = mid -1 continue s = pre_sum[end] - pre_sum[l-1] if s <= x: best_k = mid low = mid +1 else: high = mid -1 for k in range(1, best_k +1): new_l = l + k if new_l > r: continue if not dp[new_l][r]: found = True break if found: dp[l][r] = True continue # 处理右边的情况 max_possible_m = r - l +1 low = 1 high = max_possible_m best_m = 0 while low <= high: mid = (low + high) // 2 start = r - mid +1 if start < l: high = mid -1 continue s = pre_sum[r] - pre_sum[start -1] if s <= x: best_m = mid low = mid +1 else: high = mid -1 for m in range(1, best_m +1): new_r = r - m if new_r < l: continue if not dp[l][new_r]: found = True break dp[l][r] = found if dp[1][n]: print("A") else: print("B") if __name__ == "__main__": main()