結果

問題 No.1867 Partitions and Inversions
ユーザー lam6er
提出日時 2025-04-09 21:01:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,221 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 82,796 KB
実行使用メモリ 244,012 KB
最終ジャッジ日時 2025-04-09 21:02:29
合計ジャッジ時間 7,127 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    inv = [[0] * (N + 2) for _ in range(N + 2)]

    for a in range(1, N + 1):
        fenwick = [0] * (N + 2)
        current_inversions = 0
        sorted_list = []
        for b in range(a, N + 1):
            val = P[b - 1]
            cnt = len(sorted_list) - bisect.bisect_right(sorted_list, val)
            current_inversions += cnt
            inv[a][b] = current_inversions
            bisect.insort(sorted_list, val)

    T = inv[1][N]

    max_inv = [ [ -1 for _ in range(N+1) ] for __ in range(N+1) ]

    for i in range(1, N+1):
        max_inv[1][i] = inv[1][i]

    for k in range(2, N+1):
        prev = max_inv[k-1]
        current = max_inv[k]
        for i in range(k, N+1):
            mx = -1
            for j in range(k-1, i):
                temp = prev[j] + inv[j+1][i]
                if temp > mx:
                    mx = temp
            current[i] = mx

    for k in range(1, N+1):
        if k > N:
            print(0)
        else:
            print(T - max_inv[k][N])

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