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>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
using namespace std;
const int N = 8192;
short dp[N][N];
short a[N];
int n;
#define MAX(x,y) ((x)>(y)?(x):(y))
__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void up(short len, int l1, int r1, int l2, int r2)
{
l1 = max(l1, 0);
l2 = max(l2, 0);
r1 = min(r1, n-len);
r2 = min(r2, n-len);
Loop (i,l1,r1) {
short ii = i;
short iil = i + len;
Loop (j,l2,r2) {
short x1 = dp[i][j] + (a[j+len] == iil);
short x2 = dp[i][j+1] + (a[j] == iil);
short x3 = dp[i+1][j] + (a[j+len] == ii);
short x4 = dp[i+1][j+1] + (a[j] == ii);
short x12 = MAX(x1, x2);
short x34 = MAX(x3, x4);
short x1234 = MAX(x12, x34);
dp[i][j] = x1234;
}
}
}
const int S = 64;
void Do(int len)
{
for (int i = 0; i < n-len; i += S) { //for (int j = 0; j < n-len; j += S) {
for (int k = 0; k < S; k += 1)
up(len+1+k, i-k, i+S-k, 0, n);//j-k, j+S-k);
}
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n;
Loop (i,0,n) {
cin >> a[i];
--a[i];
}
Loop (i,0,n) Loop (j,0,n)
dp[i][j] = a[j] == i;
for (int i = 0; i < n-1; i += S)
Do(i);
cout << n-dp[0][0] << '\n';
}
# | 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... |