結果
問題 |
No.973 余興
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:58:41 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,973 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 82,348 KB |
実行使用メモリ | 273,436 KB |
最終ジャッジ日時 | 2025-06-12 21:02:47 |
合計ジャッジ時間 | 32,428 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | AC * 11 TLE * 1 -- * 42 |
ソースコード
n, x = map(int, input().split()) a = list(map(int, input().split())) n = len(a) pre_sum = [0] * (n + 1) for i in range(1, n + 1): pre_sum[i] = pre_sum[i - 1] + a[i - 1] # 预处理k_max k_max = [0] * (n + 2) for l in range(1, n + 1): low = 1 high = n - l + 1 best = 0 while low <= high: mid = (low + high) // 2 end = l + mid - 1 if end > n: high = mid - 1 continue s = pre_sum[end] - pre_sum[l - 1] if s <= x: best = mid low = mid + 1 else: high = mid - 1 k_max[l] = best # 预处理m_max m_max = [0] * (n + 2) for r in range(1, n + 1): low = 1 high = r best = 0 while low <= high: mid = (low + high) // 2 start = r - mid + 1 if start < 1: high = mid - 1 continue s = pre_sum[r] - pre_sum[start - 1] if s <= x: best = mid low = mid + 1 else: high = mid - 1 m_max[r] = best # 初始化dp dp = [[False] * (n + 2) for _ in range(n + 2)] # 填充dp表 for length in range(0, n): for l in range(1, n - length + 1): r = l + length if l > r: dp[l][r] = False continue possible = False # 检查左边吃k个的情况 max_k = k_max[l] for k in range(1, max_k + 1): new_l = l + k if new_l > r: continue if not dp[new_l][r]: possible = True break if possible: dp[l][r] = True continue # 检查右边吃m个的情况 max_m = m_max[r] for m in range(1, max_m + 1): new_r = r - m if new_r < l: continue if not dp[l][new_r]: possible = True break dp[l][r] = possible if dp[1][n]: print("A") else: print("B")