結果

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

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    P = list(map(int, data[1:N+1]))
    
    original_inversion = 0
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0]*(size + 2)
        def update(self, index, delta=1):
            while index <= self.size:
                self.tree[index] += delta
                index += index & -index
        def query(self, index):
            res = 0
            while index > 0:
                res += self.tree[index]
                index -= index & -index
            return res
    
    max_p = max(P)
    ft = FenwickTree(max_p)
    for i in reversed(range(N)):
        original_inversion += ft.query(P[i] - 1)
        ft.update(P[i])
    
    cross = [[0]*(N+2) for _ in range(N+2)]
    for k in range(0, N+1):
        ft = FenwickTree(max_p)
        for x in P[:k]:
            ft.update(x)
        current = 0
        cross[k][k] = 0
        for i in range(k+1, N+1):
            v = P[i-1]
            count = ft.query(max_p) - ft.query(v)
            current += count
            cross[k][i] = current
    
    dp = [[float('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] + cross[k][i] < dp[j][i]:
                    dp[j][i] = dp[j-1][k] + cross[k][i]
    
    for k in range(1, N+1):
        print(dp[k][N])
    
if __name__ == "__main__":
    main()
0