Submission #917682

#TimeUsernameProblemLanguageResultExecution timeMemory
917682406Group Photo (JOI21_ho_t3)C++17
100 / 100
138 ms77692 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = (a); i < (b); ++i) using namespace std; using ar = array<int, 2>; const int64_t INF = 1ll << 30; const int N = 5000 + 50; int dp[N], sum[N][N], cnt[N], loc[N], n, a[N]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; FOR(i, 0, n) { cin >> a[i]; --a[i]; loc[a[i]] = i; } FOR(q, 0, n) FOR(i, q + 1, n) sum[q][i] = (loc[q] > loc[i]) + sum[q][i - 1]; fill(dp, dp + N, INF); dp[0] = 0; FOR(i, 1, n) { int ct = 0; for (int j = n - 1; j >= 0; --j) if (a[j] <= i) cnt[a[j]] = ct++; int s = 0; for (int q = i; q >= 0; --q) { s -= sum[q][i]; s += cnt[q]; dp[i] = min(dp[i], (q ? dp[q - 1] : 0) + s); } } cout << dp[n - 1] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...