记录编号	441614	评测结果	AAAAAAAAAA
题目名称	拯救紫萱学姐	最终得分	100
用户昵称	xzz_233	是否通过	通过
代码语言	C++	运行时间	0.432 s
提交时间	2017-08-25 11:49:02	内存使用	39.39 MiB

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstring>
#define Fname "savemzx"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
    rg int x=0,f=1;rg char ch=getchar();
    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int maxn=1000005;
char str[maxn];
int Nxt[maxn];
int id,fir[maxn],nxt[maxn],dis[maxn];
ll w[maxn],Fir[maxn],Sec[maxn];
il vd add(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=((ll)a-b)*(a-b);}
ll ans=0;
il vd Updata(ll&a,ll&b,ll c){
    if(c>a)b=a,a=c;
    else if(c>b)b=c;
}
il vd L(int now){
    Fir[now]=Sec[now]=0;
    erep(i,now){
	L(dis[i]);
	Updata(Fir[now],Sec[now],Fir[dis[i]]+w[i]);
    }
    ans=max(ans,Fir[now]+Sec[now]);
}
int main(){
    freopen(Fname".in","r",stdin);
    freopen(Fname".out","w",stdout);
    scanf("%s",str+1);
    int len=strlen(str+1);
    Nxt[0]=0;
    Nxt[1]=0;
    rep(i,2,len){
	int k=Nxt[i-1];
	while(k&&str[k+1]!=str[i])k=Nxt[k];
	if(str[k+1]==str[i])++k;
	Nxt[i]=k;
    }
    rep(i,1,len)add(Nxt[i],i);
    L(0);
    printf("%lld\n",ans);
    return 0;
}