This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif
const int N = 5010;
int n;
int t[N];
int p[N];
int dp[N];
int nas[N];
int sum[N][N];
int wylicz(int l, int r) {
int ret = 0;
for (int i = l; i <= r; ++i) {
// ile na lewo od wartości i jest w przedziale wartości <r + 1, n>
ret += sum[i][n] - sum[i][r];
// ile na lewo od wartości i jest w przedziale wartości <l, i - 1>
ret += nas[i] - sum[i][l - 1];
}
debug(l, r, ret);
return ret;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &t[i]);
p[t[i]] = i;
}
for (int i = 1; i <= n; ++i) { // pozycja
for (int j = 1; j < i; ++j) {
if (t[j] < t[i]) {
++nas[t[i]];
}
}
for (int j = 1; j < i; ++j) {
++sum[t[i]][t[j]];
}
for (int j = 1; j <= n; ++j) {
sum[t[i]][j] += sum[t[i]][j - 1];
}
}
for (int r = 1; r <= n; ++r) {
dp[r] = 1e9;
for (int l = r; l; --l) {
dp[r] = min(dp[r], dp[l - 1] + wylicz(l, r));
}
}
printf("%d\n", dp[n]);
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
Main.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf("%d", &t[i]);
| ~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |