結果

問題 No.1867 Partitions and Inversions
ユーザー gew1fw
提出日時 2025-06-12 14:44:59
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,709 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 557,892 KB
最終ジャッジ日時 2025-06-12 14:46:26
合計ジャッジ時間 7,255 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 MLE * 1 -- * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import bisect

    N = int(sys.stdin.readline())
    P = list(map(int, sys.stdin.readline().split()))

    # Precompute the sorted version of each [l, r]
    sorted_intervals = [[0] * (N+1) for _ in range(N+1)]
    for l in range(1, N+1):
        for r in range(l, N+1):
            sorted_intervals[l][r] = sorted(P[l-1:r])

    # Initialize DP and prefix sum arrays
    INF = float('inf')
    dp = [[INF] * (N+2) for _ in range(N+2)]
    prefix = [[ [0]*(N+2) for _ in range(N+2)] for __ in range(N+2)]

    dp[0][0] = 0
    for x in range(N+2):
        prefix[0][0][x] = 0

    for j in range(1, N+1):
        for i in range(j, N+1):
            for m in range(j-1+1, i+1):
                prev_i = m-1
                prev_j = j-1
                if dp[prev_i][prev_j] == INF:
                    continue

                l = m
                r = i
                S = sorted_intervals[l][r]
                len_S = len(S)

                s_prefix = [0] * (N + 2)
                for x in range(1, N+1):
                    s_prefix[x] = bisect.bisect_right(S, x)

                cost = 0
                for s in S:
                    cnt = prev_i - prefix[prev_i][prev_j][s]
                    cost += cnt

                new_prefix = [0] * (N + 2)
                for x in range(1, N+1):
                    new_prefix[x] = prefix[prev_i][prev_j][x] + s_prefix[x]

                if dp[i][j] > dp[prev_i][prev_j] + cost:
                    dp[i][j] = dp[prev_i][prev_j] + cost
                    for x in range(N+2):
                        prefix[i][j][x] = new_prefix[x]

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

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