結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    P = list(map(int, data[1:n+1]))
    
    INF = float('inf')
    
    # Precompute cnt and sum_cnt
    cnt = [[0] * (n + 1) for _ in range(n + 1)]
    sum_cnt = [[0] * (n + 1) for _ in range(n + 1)]
    
    for l in range(1, n + 1):
        if l == 1:
            S = []
        else:
            if l == 2:
                S = [P[0]]
            else:
                pos = bisect.bisect_left(S, P[l - 2])
                S.insert(pos, P[l - 2])
        # Compute cnt[l][i] for all i
        for i in range(1, n + 1):
            if i < l:
                cnt_l_i = 0
            else:
                x = P[i - 1]
                pos = bisect.bisect_right(S, x)
                cnt_l_i = len(S) - pos
            cnt[l][i] = cnt_l_i
        # Compute sum_cnt[l][r]
        sum_so_far = 0
        for r in range(1, n + 1):
            if r >= l:
                sum_so_far += cnt[l][r]
            sum_cnt[l][r] = sum_so_far
    
    # Initialize DP
    dp = [[INF] * (n + 1) for _ in range(n + 2)]
    for i in range(1, n + 1):
        dp[1][i] = 0
    
    for k in range(2, n + 1):
        for i in range(1, n + 1):
            if i < k:
                dp[k][i] = INF
                continue
            min_val = INF
            # j can be from (k-1) to (i-1)
            for j in range(k - 1, i):
                if dp[k - 1][j] == INF:
                    continue
                current = dp[k - 1][j] + sum_cnt[j + 1][i]
                if current < min_val:
                    min_val = current
            dp[k][i] = min_val if min_val != INF else INF
    
    # Output the results
    for k in range(1, n + 1):
        print(dp[k][n] if dp[k][n] != INF else 0)

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