結果

問題 No.1867 Partitions and Inversions
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:28:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,662 bytes
コンパイル時間 268 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 333,656 KB
最終ジャッジ日時 2025-04-24 12:30:24
合計ジャッジ時間 7,044 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    P = list(map(int, data[1:n+1]))
    P = [0] + P  # 1-based indexing

    # Precompute sorted lists for each j (1-based)
    sorted_lists = []
    current = []
    for j in range(1, n+1):
        current.append(P[j])
        current.sort()
        sorted_lists.append(current.copy())

    # Precompute count[j][i] for j < i
    count = [[0]*(n+2) for _ in range(n+2)]
    for j in range(1, n+1):
        sorted_j = sorted_lists[j-1]
        for i in range(j+1, n+1):
            v = P[i]
            cnt = len(sorted_j) - bisect.bisect_right(sorted_j, v)
            count[j][i] = cnt

    # Precompute inv_count[j][i] = sum_{y=j+1 to i} count[j][y]
    inv_count = [[0]*(n+2) for _ in range(n+2)]
    for j in range(1, n+1):
        prefix = [0]*(n+2)
        for i in range(1, n+1):
            prefix[i] = prefix[i-1] + count[j][i]
        for i in range(1, n+1):
            inv_count[j][i] = prefix[i] - prefix[j]

    # Compute DP
    INF = float('inf')
    dp = [[INF]*(n+2) for _ in range(n+2)]

    # Base case: k=1, all i
    for i in range(1, n+1):
        dp[1][i] = 0

    for k in range(2, n+1):
        for i in range(k, n+1):
            min_val = INF
            for j in range(k-1, i):
                if dp[k-1][j] != INF:
                    current = dp[k-1][j] + inv_count[j][i]
                    if current < min_val:
                        min_val = current
            dp[k][i] = min_val

    # The answer for k is dp[k][n]
    for k in range(1, n+1):
        print(dp[k][n])

if __name__ == "__main__":
    main()
0