結果

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

ソースコード

diff # 

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

    # Compute cross matrix
    cross = [[0] * (N + 1) for _ in range(N + 1)]  # cross[i][j] is the number of elements in P[1..i] > P[j]
    for j in range(1, N + 1):
        current = 0
        for i in range(0, N + 1):
            if i == 0:
                cross[i][j] = 0
            else:
                cross[i][j] = cross[i - 1][j] + (1 if P[i - 1] > P[j - 1] else 0)

    # Precompute sum_after_l[l][r] = sum_{j=l+1 to r} cross[l][j]
    sum_after_l = [[0] * (N + 1) for _ in range(N + 1)]
    for l in range(N + 1):
        current_sum = 0
        for r in range(l + 1, N + 1):
            current_sum += cross[l][r]
            sum_after_l[l][r] = current_sum

    # Compute total_inv (not needed here)
    # total_inv = sum_after_l[0][N]

    # Initialize DP
    INF = float('inf')
    dp = [ [INF] * (N + 1) for _ in range(N + 1) ]
    dp[0][0] = 0

    for k in range(1, N + 1):
        for i in range(k, N + 1):
            if k == 1:
                dp[k][i] = sum_after_l[0][i]
            else:
                min_val = INF
                for j in range(k - 1, i):
                    if dp[k - 1][j] + sum_after_l[j][i] < min_val:
                        min_val = dp[k - 1][j] + sum_after_l[j][i]
                dp[k][i] = min_val

    for k in range(1, N + 1):
        print(dp[k][N])

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