记录编号	326729	评测结果	AAAAAAAWWW
题目名称	拯救紫萱学姐	最终得分	70
用户昵称	jmisnal	是否通过	未通过
代码语言	C++	运行时间	0.747 s
提交时间	2016-10-21 13:48:22	内存使用	16.53 MiB

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
int n;
char ch[1000010];
int next[1000010];
ll v[1000010];
void pre()
{
	int j,k;
	j=0;k=-1;next[0]=-1;
	while(j<n)
	{
		
		if(k==-1||ch[j]==ch[k])
			next[++j]=++k;
		else k=next[k];		
	}
}
int fa[1000010];
int find(int x)
{
	int t=x;
	while(fa[t]!=t)
	{
		t=fa[t];
	}
	return t;
}
bool isfa(int x,int y)
{
	int t=y;
	while(fa[t]!=t)
	{
		if(t==x)return 1;
		t=fa[t];
	}
	if(t==x)return 1;
	return 0;
}
ll big[1001];
void change()
{
	for(int i=2;i<1000;i++)
		big[i-1]=big[i];
	big[0]--;
}
void work()
{
//	ll big1=0,big2=0;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=0;i<n;i++)
	{
		if(next[i+1]==0)
			v[i]=(i+1)*(i+1);			
		else
		{
			v[i]=((i+1)-next[i+1])*((i+1)-next[i+1])+v[next[i+1]-1];
			fa[i+1]=next[i+1];
		}

		int w=lower_bound(big+1,big+big[0]+1,v[i])-big;
		if(w>big[0])
		{
			
			big[0]++;
			if(big[0]>=1000)
				change();
			big[big[0]]=v[i];
		}
	}
	ll ans=0;
	for(int i=1;i<=big[0];i++)
	{
		for(int j=i+1;j<=big[0];j++)
		{
			if(isfa(i,j))
				ans=max(ans,big[j]);
			else if(isfa(j,i))
				ans=max(ans,big[i]);
			else
				ans=max(ans,big[i]+big[j]);
		}
	}
	printf("%lld",ans);
	//	cout<<i<<' '<<fa[i]<<endl;
//	printf("%lld",big1+big2);
}
int main()
{
//	freopen("abcd.in","r",stdin);
	freopen("savemzx.in","r",stdin);
	freopen("savemzx.out","w",stdout);
	char c=getchar();
	while(c<'a'||c>'z')c=getchar();
	while(c>='a'&&c<='z')
	{
		ch[n++]=c;
		c=getchar();
	}
	pre();
//	cout<<lower_bound(big+1,big+big[0]+1,1)-big;
//	return 0;
//	for(int i=1;i<=n;i++)
//		cout<<next[i]<<' ';
//	cout<<endl;
	work();
	return 0;
}