Submission #2101403

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,b,a) for(int i=b;i>=a;i--)
#define efo(i,u,v) for(int i=BB[u],v=B[BB[u]][1];i;v=B[i=B[i][0]][1])
#define mset(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
char ch;
int read(){int n=0,p=1;for(ch=getchar();ch<'0' || '9'<ch;ch=getchar())if(ch=='-') p=-1;for(;'0'<=ch && ch<='9';ch=getchar()) n=n*10+ch-'0';return n*p;}
const int N=205,M=2e7+5;
int n,m,a[N],d[N<<1],pr[M];
bool b[M],c[M],bz[M];
void prep()
{
	mset(bz,1);
	bz[0]=bz[1]=0;
	fo(i,2,m)
	{
		if(bz[i]) pr[++pr[0]]=i;
		fo(j,1,pr[0])
		{
			ll x=(ll)i*pr[j];
			if(x>m) break;
			bz[x]=0;
			if(i%pr[j]==0) break;
		}
	}
}

const int V=N<<3,INF=1e9;
const int E=10*V*V;
int B0,S,T,BB[V];
ll ans,dis[V],B[E][4];
bool vis[V];
void link(int u,int v,int r,ll w)
{
	B[++B0][1]=v,B[B0][2]=r,B[B0][3]=w,B[B0][0]=BB[u],BB[u]=B0;
	if(!(B0&1)) link(v,u,0,-w);
}
ll aug(int v,ll flow)
{
	vis[v]=1;
	if(v==T)
	{
		ans+=dis[S]*flow;
		return flow;
	}
	efo(i,v,u)
		if(B[i][2] && !vis[u] && dis[v]==dis[u]+B[i][3])
		{
			ll f=aug(u,min(flow,B[i][2]));
			if(f)
			{
				B[i][2]-=f,B[i^1][2]+=f;
				return f;
			}
		}
	return 0;
}
bool change()
{
	ll minh=INF;
	fo(u,S,T) if(vis[u])
		efo(i,u,v) if(!vis[v])
			if(B[i][2]) minh=min(minh,dis[v]+B[i][3]-dis[u]);
	if(minh==INF) return 0;
	fo(i,S,T) if(vis[i]) dis[i]+=minh,vis[i]=0;
	return 1;
}
int main()
{
	n=read();
	fo(i,1,n) b[a[i]=read()]=1,m=max(m,a[i]);
	++m;
	prep();
	fo(i,1,m) c[i]=b[i]^b[i-1];
	fo(i,1,m) if(c[i]) d[++d[0]]=i;
	
	B0=1,S=0,T=d[0]+d[0]+1;
	fo(i,1,d[0]-1)
		fo(j,i+1,d[0])
		{
			if((d[j]-d[i])%2==0) link(i,d[0]+j,1,2),link(j,d[0]+i,1,2);
			else
			if(bz[d[j]-d[i]]) link(i,d[0]+j,1,1),link(j,d[0]+i,1,1);
			else link(i,d[0]+j,1,3),link(j,d[0]+i,1,3);
		}
	fo(i,1,d[0]) link(S,i,1,0),link(d[0]+i,T,1,0);
	
	do
	{
		while(aug(S,INF)) mset(vis,0);
	}
	while(change());
	printf("%lld",ans/2);
	return 0;
}

Submission Info

Judge Result