Submission #637587

#TimeUsernameProblemLanguageResultExecution timeMemory
637587danikoynovGroup Photo (JOI21_ho_t3)C++14
64 / 100
5037 ms360 KiB
/** ____ ____ ____ ____ ____ ____ ||l |||e |||i |||n |||a |||d || ||__|||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\|/__\| **/ #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int maxn = 5010; int n, a[maxn], dp[maxn], pos[maxn], fen[maxn]; void add(int pos, int val) { for (int i = pos; i <= n; i += (i & -i)) fen[i] += val; } int query(int pos) { int s = 0; for (int i = pos; i > 0; i -= (i & -i)) s += fen[i]; return s; } void solve() { 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] = n * n; for (int j = 0; j < i; j ++) { if (j > 0) add(pos[j], 1); int st = j + 1, sum = 0; for (int k = i; k > j; k --) { ll cur = pos[k] + (j + (i - k) - query(pos[k] - 1)); ///cout << i << " " << j << " " << k << " " << cur << endl; add(pos[k], 1); cur -= st; st ++; sum = sum + max((ll)0, cur); } for (int k = i; k > j; k --) add(pos[k], - 1); ///cout << i << " " << j << " " << sum << endl; dp[i] = min(dp[i], dp[j] + sum); } for (int j = 0; j < i; j ++) if (j > 0) add(pos[j], - 1); ///cout << i << " -- " << dp[i] << endl; } cout << dp[n] << endl; } int main() { solve(); 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...