結果

問題 No.1867 Partitions and Inversions
ユーザー gew1fw
提出日時 2025-06-12 14:49:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,540 bytes
コンパイル時間 145 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 226,716 KB
最終ジャッジ日時 2025-06-12 14:52:47
合計ジャッジ時間 6,896 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()))
    
    # Precompute inv[l][r] for all 1 <= l <= r <= N
    inv = [[0]*(N+1) for _ in range(N+1)]  # 1-based
    
    for l in range(1, N+1):
        fenwick = [0]*(N+2)  # 1-based to N
        total = 0
        for r in range(l, N+1):
            x = P[r-1]
            # count number of elements already in the Fenwick tree > x
            # which is (current_size) - query(x)
            current_size = r - l
            pos = x
            res = current_size
            while pos > 0:
                res -= fenwick[pos]
                pos -= pos & -pos
            total += res
            # update Fenwick tree
            pos = x
            while pos <= N:
                fenwick[pos] += 1
                pos += pos & -pos
            inv[l][r] = total
    
    original = inv[1][N]
    
    # Initialize DP
    max_k = N
    dp = [ [ -float('inf') ]*(N+2) for _ in range(max_k+2) ]
    dp[0][0] = 0
    
    for j in range(1, max_k+1):
        current_dp = [ -float('inf') ]*(N+2)
        for i in range(1, N+1):
            for l in range(0, i):
                val = dp[j-1][l] + inv[l+1][i]
                if val > current_dp[i]:
                    current_dp[i] = val
        dp[j] = current_dp
    
    for k in range(1, N+1):
        max_sum = max(dp[k][i] for i in range(N+1))
        ans = original - max_sum
        print(ans)
    
if __name__ == '__main__':
    main()
0