結果
問題 |
No.2423 Merge Stones
|
ユーザー |
![]() |
提出日時 | 2025-05-14 13:22:59 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,147 bytes |
コンパイル時間 | 638 ms |
コンパイル使用メモリ | 82,912 KB |
実行使用メモリ | 128,484 KB |
最終ジャッジ日時 | 2025-05-14 13:25:04 |
合計ジャッジ時間 | 6,642 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 TLE * 1 -- * 61 |
ソースコード
import sys def solve(): N, K = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) C = list(map(int, sys.stdin.readline().split())) # Using -1 to represent "not possible" since A_i >= 1, so valid sums are positive. neg_inf = -1 # dp[length][start_idx][color_idx] # color_idx is 0-indexed (color_value - 1) # MaxColor is 50. Indices 0 to 49. dp = [[[neg_inf] * 50 for _ in range(N)] for _ in range(N + 1)] max_overall_power = 0 # Since all A_i >= 1, min possible positive power is 1. # Base cases: segments of length 1 for i in range(N): color_val = C[i] color_idx = color_val - 1 # Convert to 0-indexed dp[1][i][color_idx] = A[i] if A[i] > max_overall_power: max_overall_power = A[i] # Iterate over segment lengths for length in range(2, N + 1): # Iterate over starting index of the segment for i in range(N): # Iterate over split point (k_len is length of the left part) for k_len in range(1, length): left_start_idx = i left_len = k_len right_start_idx = (i + k_len) % N right_len = length - k_len # Iterate over color of the left merged part for lc_idx in range(50): val_left = dp[left_len][left_start_idx][lc_idx] if val_left == neg_inf: continue # Iterate over color of the right merged part, # ensuring it's compatible with left_color. # abs(left_color_val - right_color_val) <= K # abs((lc_idx+1) - (rc_idx+1)) <= K => abs(lc_idx - rc_idx) <= K # So, rc_idx must be in [lc_idx - K, lc_idx + K] min_compatible_rc_idx = max(0, lc_idx - K) max_compatible_rc_idx = min(49, lc_idx + K) for rc_idx in range(min_compatible_rc_idx, max_compatible_rc_idx + 1): val_right = dp[right_len][right_start_idx][rc_idx] if val_right == neg_inf: continue current_sum = val_left + val_right # The new merged stone (segment of `length` starting at `i`) # can take color of left part (lc_idx) or right part (rc_idx). if current_sum > dp[length][i][lc_idx]: dp[length][i][lc_idx] = current_sum if current_sum > dp[length][i][rc_idx]: dp[length][i][rc_idx] = current_sum # Update overall maximum power found if current_sum > max_overall_power: max_overall_power = current_sum print(max_overall_power) solve()