結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    P = list(map(int, input[idx:idx+N]))
    idx += N

    # Precompute C[j][i]
    C = [[0] * (N + 1) for _ in range(N + 1)]
    for j in range(N + 1):
        if j == 0:
            for i in range(1, N + 1):
                C[j][i] = 0
        else:
            # Take elements from P[0] to P[j-1] (1-based to j)
            sorted_list = sorted(P[:j])
            cnts = [0] * (N + 1)
            for y in range(j + 1, N + 1):
                val = P[y - 1]
                cnt = len(sorted_list) - bisect.bisect_right(sorted_list, val)
                cnts[y] = cnt
            # Compute prefix sums
            prefix = 0
            for i in range(j + 1, N + 1):
                prefix += cnts[i]
                C[j][i] = prefix

    # Initialize DP
    INF = float('inf')
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        dp[1][i] = 0  # One block, no cross inversions

    for k in range(2, N + 1):
        for i in range(k, N + 1):
            min_val = INF
            # j must be >= k-1 (since previous k-1 blocks need at least k-1 elements)
            for j in range(k-1, i):
                current = dp[k-1][j] + C[j][i]
                if current < min_val:
                    min_val = current
            dp[k][i] = min_val

    for k in range(1, N + 1):
        print(dp[k][N])

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