| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 855530 | tvladm2009 | Giraffes (JOI22_giraffes) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 8000 + 7;
int a[N], pos[N], dp[N][N][307];
int main() {
#ifdef ONPC
freopen("input.txt", "r", stdin);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pos[a[i]] = i;
}
for (int len = 1; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
for (int t = 1; t <= 300 && t + len - 1 <= n; t++) {
int r = l + len - 1;
int tt = t + len - 1;
if (a[l] == t) {
dp[len][l][t] = dp[len - 1][l + 1][t + 1] + 1;
} else if (a[r] == t) {
dp[len][l][t] = dp[len - 1][l][t + 1] + 1;
} else if (a[l] == tt) {
dp[len][l][t] = dp[len - 1][l + 1][t] + 1;
} else if (a[r] == tt) {
dp[len][l][t] = dp[len - 1][l][t] + 1;
} else {
dp[len][l][t] = max({dp[len - 1][l][t], dp[len - 1][l + 1][t], dp[len - 1][l][t + 1], dp[len - 1][l + 1][t + 1]});
}
}
}
}
cout << n - dp[n][1][1] << "\n";
return 0;
}