結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    P = list(map(int, input[idx:idx+N]))
    idx += N

    # Precompute A_j for each j, where A_j is the sorted list of P[0..j-1]
    A = []
    for j in range(N+1):
        if j == 0:
            A_j = []
        else:
            A_j = sorted(P[:j])
        A.append(A_j)
    
    # Precompute cross[j][i] for j < i
    cross = [[0]*(N+2) for _ in range(N+2)]  # cross[j][i] for j < i
    for j in range(N):
        B = []
        for i in range(j+1, N+1):
            if i-1 < len(P):
                x = P[i-1]
                bisect.insort(B, x)
            # Compute sum_cross
            sum_cross = 0
            for x in A[j]:
                cnt = bisect.bisect_left(B, x)
                sum_cross += cnt
            cross[j][i] = sum_cross
    
    # Initialize DP
    INF = float('inf')
    dp = [[INF]*(N+2) for _ in range(N+2)]
    dp[0][0] = 0
    
    for m in range(1, N+1):
        for i in range(m, N+1):
            min_val = INF
            # j must be at least m-1, and less than i
            start_j = m-1
            end_j = i-1
            for j in range(start_j, end_j +1):
                if dp[m-1][j] == INF:
                    continue
                current = dp[m-1][j] + cross[j][i]
                if current < min_val:
                    min_val = current
            if min_val != INF:
                dp[m][i] = min_val
    
    for k in range(1, N+1):
        print(dp[k][N])

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