結果

問題 No.1867 Partitions and Inversions
ユーザー qwewe
提出日時 2025-05-14 12:52:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,102 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 82,020 KB
実行使用メモリ 226,340 KB
最終ジャッジ日時 2025-05-14 12:54:46
合計ジャッジ時間 6,901 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 = [p - 1 for p in P]  # Convert to 0-based index

    # Precompute inv[a][b] for all a <= b
    inv = [[0] * N for _ in range(N)]
    for a in range(N):
        fenwick = [0] * (N + 2)
        cnt = 0
        for b in range(a, N):
            # Insert P[b] into the Fenwick tree
            # Query the number of elements > P[b]
            val = P[b] + 1  # 1-based
            res = 0
            x = val + 1
            while x <= N:
                res += fenwick[x]
                x += x & -x
            cnt += res
            inv[a][b] = cnt
            # Update Fenwick tree
            x = val
            while x > 0:
                fenwick[x] += 1
                x -= x & -x

    total_inversions = inv[0][N-1]

    # Now, compute the DP using Knuth's optimization
    # dp[k][i] = max sum of inv in k intervals for first i elements
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    # For k=1, dp[1][i] = inv[0][i-1] (since a is 0-based)
    for i in range(1, N + 1):
        dp[1][i] = inv[0][i-1]

    # Knuth's optimization
    for k in range(2, N + 1):
        # We need to compute dp[k][i] for i from k to N
        # Using the fact that the optimal j for i is >= the optimal j for i-1
        # We'll use a helper array to track the optimal j for each i
        # Initialize for each i, the optimal j is between [k-1, i-1]
        for i in range(k, N + 1):
            max_val = -1
            best_j = 0
            start_j = k-1 if i == k else max(k-1, 1)
            for j in range(k-1, i):
                current_val = dp[k-1][j] + inv[j][i-1]
                if current_val > max_val:
                    max_val = current_val
                    best_j = j
            dp[k][i] = max_val

    # Compute the answers
    for k in range(1, N + 1):
        if k > N:
            print(0)
            continue
        S_k = dp[k][N]
        ans = total_inversions - S_k
        print(ans)

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