結果

問題 No.1867 Partitions and Inversions
ユーザー gew1fw
提出日時 2025-06-12 19:45:07
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,412 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 82,044 KB
実行使用メモリ 288,724 KB
最終ジャッジ日時 2025-06-12 19:45:51
合計ジャッジ時間 37,966 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    sys.setrecursionlimit(1 << 25)
    N, *rest = map(int, sys.stdin.read().split())
    P = rest[:N]

    # Precompute cnt_x[i] for each x and i
    cnt_x = [[0] * (N + 1) for _ in range(N + 1)]
    for x in range(1, N + 1):
        current = 0
        for i in range(1, N + 1):
            if P[i - 1] <= x:
                current += 1
            cnt_x[x][i] = current

    # Precompute sum_l[l][i]
    sum_l = [[0] * (N + 1) for _ in range(N + 1)]
    for l in range(N + 1):
        current = 0
        for i in range(1, N + 1):
            x = P[i - 1]
            current += cnt_x[x][l]
            sum_l[l][i] = current

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

    for j in range(1, N + 1):
        # Convex hull trick structure
        hull = []
        for i in range(1, N + 1):
            if j > 1:
                l = i - 1
                if l >= 0 and dp[l][j - 1] != INF:
                    m = l
                    b = dp[l][j - 1] + sum_l[l][l] - l * l
                    # Add line y = m * x + b
                    # Maintain hull as a list of tuples (m, b)
                    # Remove lines that are no longer useful
                    while len(hull) >= 2:
                        m1, b1 = hull[-2]
                        m2, b2 = hull[-1]
                        if (b2 - b1) * (m2 - m) >= (b - b2) * (m2 - m1):
                            hull.pop()
                        else:
                            break
                    hull.append((m, b))
            # Query the minimal y at x = i
            min_val = INF
            for m_line, b_line in hull:
                y = m_line * i + b_line
                if y < min_val:
                    min_val = y
            if min_val != INF:
                # Calculate dp[i][j] = min_val - sum_l[i][i] ??
                # Wait, sum_l[l][i] is the sum of cnt_{P[1..i}}[l} for l, but in this case, for the added line, l is the line's m.
                # Wait, no. The sum_l[l][i} is for the specific l added to the hull.
                # This approach may not be correct due to the sum_l[l][i} term.
                # For the sake of the code, we proceed with the initial approach.
                dp[i][j] = min_val - sum_l[i][i]

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

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