結果

問題 No.1867 Partitions and Inversions
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:41:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,294 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 83,008 KB
実行使用メモリ 296,760 KB
最終ジャッジ日時 2025-06-12 14:41:57
合計ジャッジ時間 6,807 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    P = list(map(int, sys.stdin.readline().split()))
    P = [0] + P  # 1-based indexing

    # Precompute sum_greater: sum_greater[k][j] = number of a <=k where P[a] > P[j]
    sum_greater = [[0] * (N + 2) for _ in range(N + 2)]
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            if P[k] > P[j]:
                sum_greater[k][j] = sum_greater[k-1][j] + 1
            else:
                sum_greater[k][j] = sum_greater[k-1][j]

    # Precompute inv_pairs: for each k, i, inv_pairs[k][i] is sum of sum_greater[k][j] for j=k+1 to i
    inv_pairs = [[0] * (N + 2) for _ in range(N + 2)]
    for k in range(1, N + 1):
        for i in range(k + 1, N + 1):
            inv_pairs[k][i] = inv_pairs[k][i-1] + sum_greater[k][i]

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

    for j in range(2, N+1):
        for i in range(j, N+1):
            for k in range(j-1, i):
                if dp[j-1][k] + inv_pairs[k][i] < dp[j][i]:
                    dp[j][i] = dp[j-1][k] + inv_pairs[k][i]

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

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