Submission #38147532

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
//#define int long long
void chkmax(int &a,int b) {a=a>b?a:b;}
void chkmin(int &a,int b) {a=a<b?a:b;}
int read() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=(ch=='-'?-1:f),ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int a[6010],f[2010][2010],g[2010],mx;
signed main() {
	int n=read(),m=n*3,cnt=0;
	for(int i=1;i<=m;i++)
		a[i]=read();
	memset(f,-0x3f,sizeof(f));
	memset(g,-0x3f,sizeof(g));
	f[a[1]][a[2]]=f[a[2]][a[1]]=0;
	g[a[1]]=g[a[2]]=0,mx=0;
	for(int i=3;i<m;i+=3) {
		array<int,3> p={a[i],a[i+1],a[i+2]};
		sort(p.begin(),p.end());
		if(p[0]==p[2]) {cnt++;continue;}
		vector<pair<pair<int,int>,int> > ch;
		auto add=[&](int x,int y,int val) {
			ch.push_back({{x,y},val});
			ch.push_back({{y,x},val});
		};
		if(p[1]==p[2]) swap(p[0],p[2]);
		if(p[0]==p[1]) {
			for(int i=1;i<=n;i++)
				add(i,p[2],f[i][p[0]]+1);
		}
		for(int i=0;i<3;i++) {
			vector<int> q;
			for(int j=0;j<3;j++)
				if(i!=j) q.push_back(p[j]);
			add(q[0],q[1],f[p[i]][p[i]]+1);
		}
		for(int i=0;i<3;i++) {
			for(int j=1;j<=n;j++) {
				bool flag=0;
				for(int k=0;k<3;k++)
					if(i!=k&&j==p[k]) flag=1;
				if(flag) add(p[i],j,mx);
				else add(p[i],j,g[j]);
			}
		}
		for(auto [x,val]:ch) {
			chkmax(f[x.first][x.second],val);
			chkmax(g[x.first],val),chkmax(g[x.second],val);
			chkmax(mx,val);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			chkmax(ans,f[i][j]+(i==a[m]&&j==a[m]));
	printf("%d\n",ans+cnt);
	return 0;
}

Submission Info

Judge Result