結果
問題 | No.1867 Partitions and Inversions |
ユーザー |
|
提出日時 | 2022-03-04 23:01:45 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,175 ms / 5,000 ms |
コード長 | 933 bytes |
コンパイル時間 | 7,126 ms |
コンパイル使用メモリ | 163,124 KB |
実行使用メモリ | 58,496 KB |
最終ジャッジ日時 | 2024-07-18 21:39:08 |
合計ジャッジ時間 | 86,144 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 65 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/segtree> using namespace std; const int MAXN = 3000; int N, P[MAXN]; int inv[MAXN][MAXN]; int DP[MAXN][MAXN]; int add(int a, int b) { return a + b; } int zero() { return 0; } using Seg = atcoder::segtree<int, add, zero>; int main() { cin >> N; for (int i = 0; i < N; ++i) cin >> P[i]; for (int i = 0; i < N; ++i) { Seg seg(N); int ret = 0; for (int j = i; j < N; ++j) { ret += seg.prod(P[j] - 1, N); seg.set(P[j] - 1, 1); inv[i][j] = ret; } } for (int i = 0; i < N; ++i) DP[i][0] = inv[0][i]; for (int i = 0; i < N; ++i) for (int j = i + 1; j < N; ++j) for (int k = 0; k <= i; ++k) DP[j][k + 1] = max(DP[j][k + 1], DP[i][k] + inv[i + 1][j]); for (int i = 0; i < N; ++i) cout << inv[0][N - 1] - DP[N - 1][i] << endl; }