結果
問題 |
No.1867 Partitions and Inversions
|
ユーザー |
![]() |
提出日時 | 2025-04-24 12:31:17 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,776 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 82,776 KB |
実行使用メモリ | 697,000 KB |
最終ジャッジ日時 | 2025-04-24 12:32:49 |
合計ジャッジ時間 | 7,090 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | AC * 2 MLE * 1 -- * 62 |
ソースコード
import bisect def main(): import sys input = sys.stdin.read().split() N = int(input[0]) P = list(map(int, input[1:N+1])) # Precompute sorted segments and their prefix sums sorted_segments = [[[] for _ in range(N)] for _ in range(N)] for l in range(N): current = [] for r in range(l, N): current.append(P[r]) sorted_seg = sorted(current) sorted_segments[l][r] = sorted_seg # Precompute the original inversion count original_inv = 0 for i in range(N): for j in range(i+1, N): if P[i] > P[j]: original_inv += 1 # Initialize DP dp = [ [float('inf')] * (N + 1) for _ in range(N + 1) ] dp[0][0] = 0 # 0 segments, 0 elements # merged[k][i] stores the sorted list of elements up to i with k segments merged = [ [ [] for _ in range(N + 1) ] for _ in range(N + 1) ] merged[0][0] = [] for k in range(1, N + 1): for i in range(1, N + 1): for j in range(i): if dp[k-1][j] == float('inf'): continue l = j r = i - 1 if l > r: continue seg = sorted_segments[l][r] prev_merged = merged[k-1][j] inv_count = 0 # Compute inv_count between prev_merged and seg ptr_prev = len(prev_merged) - 1 for x in reversed(seg): while ptr_prev >= 0 and prev_merged[ptr_prev] > x: ptr_prev -= 1 inv_count += (len(prev_merged) - ptr_prev - 1) total_cost = dp[k-1][j] + inv_count if total_cost < dp[k][i]: dp[k][i] = total_cost # Merge prev_merged and seg new_merged = [] p1 = 0 p2 = 0 while p1 < len(prev_merged) and p2 < len(seg): if prev_merged[p1] <= seg[p2]: new_merged.append(prev_merged[p1]) p1 += 1 else: new_merged.append(seg[p2]) p2 += 1 new_merged += prev_merged[p1:] new_merged += seg[p2:] merged[k][i] = new_merged # After processing all i for this k, fill the answer for k # The answer for k is the minimum of dp[k][N] and the original_inv if k == N if k == N: ans = original_inv else: ans = dp[k][N] if dp[k][N] != float('inf') else original_inv print(ans) if __name__ == "__main__": main()