Submission #1182651

#TimeUsernameProblemLanguageResultExecution timeMemory
1182651anteknneGroup Photo (JOI21_ho_t3)C++20
44 / 100
5094 ms328 KiB
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; #define pb push_back #define pii pair<ll, ll> #define pll pair<ll, ll> #define st first #define nd second #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> #define debug false const int MAXN = 5000; int a[MAXN + 1]; int dp[MAXN + 1]; int pos[MAXN + 1]; int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i ++) { cin >> a[i]; pos[a[i]] = i; } for (int i = 1; i <= n; i ++) { dp[i] = INT_MAX; } dp[0] = 0; for (int i = 1; i <= n; i ++) { for (int j = 0; j < i; j ++) { int cnt = 0; for (int k = j + 1; k <= i; k ++) { for (int l = j + 1; l < k; l ++) { cnt += (pos[k] > pos[l]); } } //cout << cnt << "\n"; for (int k = 1; k <= j; k ++) { for (int l = j + 1; l <= i; l ++) { cnt += (pos[k] > pos[l]); } } dp[i] = min(dp[i], dp[j] + cnt); //cout << cnt << "\n"; } } cout << dp[n] << "\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...