結果

問題 No.1867 Partitions and Inversions
ユーザー qwewe
提出日時 2025-05-14 12:57:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,776 bytes
コンパイル時間 486 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 52,480 KB
最終ジャッジ日時 2025-05-14 12:59:15
合計ジャッジ時間 7,584 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0