题目传送门：CF2003F Turtle and Three Sequences。
首先如果 \(b\) 的值域很小我们就可以考虑状压，考虑对 \(b\) 的值域的每一个数染上一个 \([0,m-1]\) 的值，这样 \(b_i = b_j\) 映射后一定也满足，但是 \(b_i \neq b_j\) 不一定映射后满足，说明这个随机化求出的答案一定合法但不一定最优。
我们考虑随机 \(T\) 次来计算概率，一次成功的概率显然为 \(\frac{5!}{5^5} = 3.84\%\)，那么 \(T\) 次成功的概率显然为 \(1-(1-3.84\%)^T\)，取 \(T=100\) 几乎就是 \(100\%\)。
考虑如何计算答案，设 \(f_{i,j,S}\) 表示前 \(i\) 个位置，最后选择的一个位置的 \(a\) 值为 \(j\) 且选择的 \(b\) 的状态为 \(S\)。
\[f_{i,a_i,S} = \max_{k\le a_i,w_{b_i}\in S} \{f_{i-1,k,S \backslash {w_{b_i}}} + c_i\}
\]
利用滚动数组和树状数组优化一下即可，复杂度 \(O(Tn2^m\log n)\)。
#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
inline int read(){char c=getchar();int f=1,ans=0;while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();return ans*f;
}
const int N=3010,M=1<<5;
mt19937_64 randd(time(0));
int n,m,a[N],b[N],c[N],w[N],f[M];
struct tree{int c[N];#define lowbit(x) x&-xinline void add(int i,int x){for (;i<=n;i+=lowbit(i)) c[i]=max(c[i],x);}inline int sum(int i){int ans=-1e18;for (;i;i-=lowbit(i)) ans=max(ans,c[i]);return ans;}
}t[M];
inline int solve(){for (int i=1;i<=n;i++) w[i]=randd()%m;for (int i=0;i<(1<<m);i++) for (int j=1;j<=n;j++) t[i].c[j]=-1e18;int ans=-1e18;for (int i=1;i<=n;i++){for (int j=0;j<(1<<m);j++) f[j]=-1e18;f[1<<w[b[i]]]=c[i];for (int j=0;j<(1<<m);j++) if ((j>>w[b[i]])&1) f[j]=max(f[j],t[j^(1<<w[b[i]])].sum(a[i])+c[i]);for (int j=0;j<(1<<m);j++) t[j].add(a[i],f[j]);ans=max(ans,f[(1<<m)-1]);}return ans;
}
main(){n=read(),m=read();for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<=n;i++) b[i]=read();for (int i=1;i<=n;i++) c[i]=read();int T=100,ans=-1e18;while(T--) ans=max(ans,solve());if (ans<=0) puts("-1"); else cout <<ans;return 0;
}