結果

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

ソースコード

diff # 

import sys

def solve():
    N = int(sys.stdin.readline())
    P_orig = list(map(int, sys.stdin.readline().split()))

    # P is 1-indexed for problem logic alignment
    P = [0] + P_orig 

    class FenwickTree:
        def __init__(self, size):
            self.tree = [0] * (size + 1)
            self.size = size 

        def update(self, idx, delta):
            while idx <= self.size:
                self.tree[idx] += delta
                idx += idx & (-idx)

        def query(self, idx):
            s = 0
            while idx > 0:
                s += self.tree[idx]
                idx -= idx & (-idx)
            return s

        def query_count_greater_than(self, val):
            if val >= self.size:
                return 0
            total_items_in_ft = self.query(self.size) 
            count_leq_val = self.query(val)
            return total_items_in_ft - count_leq_val

    cost = [[0] * (N + 1) for _ in range(N + 1)]

    for l in range(1, N + 1):
        ft = FenwickTree(N) 
        current_segment_inversions = 0
        for r in range(l, N + 1):
            inversions_with_Pr = ft.query_count_greater_than(P[r])
            current_segment_inversions += inversions_with_Pr
            cost[l][r] = current_segment_inversions
            ft.update(P[r], 1)

    total_inv = cost[1][N]

    dp = [[-1] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    
    for k_val in range(1, N + 1):
        for i in range(1, N + 1):
            if i < k_val:
                continue 
            
            max_removed_for_this_state = -1
            min_j_loop_start = k_val - 1 
            
            for j in range(min_j_loop_start, i): 
                if dp[k_val - 1][j] != -1:
                    current_block_cost = cost[j + 1][i]
                    current_removed = dp[k_val - 1][j] + current_block_cost
                    if current_removed > max_removed_for_this_state:
                        max_removed_for_this_state = current_removed
            dp[k_val][i] = max_removed_for_this_state
            
    output_lines = []
    for k_ans in range(1, N + 1):
        max_removed_total = dp[k_ans][N]
        # dp[k_ans][N] should always be >= 0 since costs are non-negative 
        # and dp[0][0]=0. A value of -1 would mean an issue or unreachable state,
        # but all (k_ans, N) states are reachable for 1 <= k_ans <= N.
        ans = total_inv - max_removed_total
        output_lines.append(str(ans))
            
    sys.stdout.write("\n".join(output_lines) + "\n")

solve()
0