結果
問題 |
No.1867 Partitions and Inversions
|
ユーザー |
![]() |
提出日時 | 2025-06-12 14:41:46 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,294 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 83,008 KB |
実行使用メモリ | 296,760 KB |
最終ジャッジ日時 | 2025-06-12 14:41:57 |
合計ジャッジ時間 | 6,807 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | AC * 2 TLE * 1 -- * 62 |
ソースコード
import sys def main(): sys.setrecursionlimit(1 << 25) N = int(sys.stdin.readline()) P = list(map(int, sys.stdin.readline().split())) P = [0] + P # 1-based indexing # Precompute sum_greater: sum_greater[k][j] = number of a <=k where P[a] > P[j] sum_greater = [[0] * (N + 2) for _ in range(N + 2)] for j in range(1, N + 1): for k in range(1, N + 1): if P[k] > P[j]: sum_greater[k][j] = sum_greater[k-1][j] + 1 else: sum_greater[k][j] = sum_greater[k-1][j] # Precompute inv_pairs: for each k, i, inv_pairs[k][i] is sum of sum_greater[k][j] for j=k+1 to i inv_pairs = [[0] * (N + 2) for _ in range(N + 2)] for k in range(1, N + 1): for i in range(k + 1, N + 1): inv_pairs[k][i] = inv_pairs[k][i-1] + sum_greater[k][i] # Initialize DP INF = float('inf') dp = [ [INF] * (N + 2) for _ in range(N + 2) ] for i in range(1, N+1): dp[1][i] = 0 for j in range(2, N+1): for i in range(j, N+1): for k in range(j-1, i): if dp[j-1][k] + inv_pairs[k][i] < dp[j][i]: dp[j][i] = dp[j-1][k] + inv_pairs[k][i] for k in range(1, N+1): print(dp[k][N]) if __name__ == '__main__': main()