记录编号	477420	评测结果	AAAAAAAAAAAAAAA
题目名称	乐曲主题	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.141 s
提交时间	2017-12-02 22:14:56	内存使用	0.49 MiB

#include<bits/stdc++.h>
using namespace std;
const int inf=5005;
int n,m,a[inf];
int rank[inf],sa[inf],h1[inf],h2[inf],cnt[inf],tem[inf],c[inf][2];
bool cmp(int x,int y){
	return c[x][0]==c[y][0]&&c[x][1]==c[y][1];
}
bool Cmp(int a,int b,int x){
	if(a<b){
		if(a+x>=b)return 0;
	}
	else {
		if(b+x>=a)return 0;
	}
	return 1;
}
bool check(int x){
	for(int i=1;i+x-1<=n;i++){
		if(h1[i]<x&&h2[rank[i]+1]<x)continue;
		if(h1[i]>=x){
			int now=i;
			while(h1[now]>=x&&rank[now]>1){
	//			if(x==10)cout<<i<<" "<<sa[rank[now]-1]<<endl;
				if(Cmp(i,sa[rank[now]-1],x))return 1;
				now=sa[rank[now]-1];
			}
		}
		if(h2[rank[i]+1]>=x){
			int now=i;
			while(h2[rank[now]+1]>=x&&rank[now]<n){
				if(Cmp(i,sa[rank[now]+1],x))return 1;
				now=sa[rank[now]+1];
			}
		}
	}
	return 0;
}
int main()
{
	freopen("theme.in","r",stdin);
	freopen("theme.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d",&n);
	int last;
	scanf("%d",&last);
	n--;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		a[i]=rank[i]=last-x+100;
		last=x;
	}
	for(int i=1;i<=n;i++)cnt[rank[i]]++;
	m=200;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)sa[cnt[rank[i]]--]=i;
	for(int l=1;l<n;l<<=1){
		int p=0;
		for(int i=n-l+1;i<=n;i++)c[i][0]=0,tem[++p]=i;
		for(int i=1;i<=n;i++){
			c[i][1]=rank[i];
			if(sa[i]>l){
				c[sa[i]-l][0]=rank[sa[i]];
				tem[++p]=sa[i]-l;
			}
		}
		for(int i=1;i<=m;i++)cnt[i]=0;
		for(int i=1;i<=n;i++)cnt[rank[tem[i]]]++;
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[rank[tem[i]]]--]=tem[i];
		p=0;
		for(int i=1;i<=n;i++)rank[sa[i]]=cmp(sa[i],sa[i-1])?p:++p;
		if(p==n)break;
		m=p;
	}
	int k=0;
	sa[0]=0;
	for(int i=1;i<=n;i++){
		if(k)k--;
		int j=sa[rank[i]-1];
		while(a[j+k]==a[i+k])k++;
		h1[i]=k;
	}//cout<<sa[rank[1]-1];
	for(int i=1;i<=n;i++)h2[rank[i]]=h1[i];
	int l=4,r=n;
//	for(int i=1;i<=n;i++)cout<<h1[i]<<" ";
	while(l!=r){
		int mid=((l+r)>>1)+1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	if(check(l))printf("%d\n",l+1);
	else printf("%d\n",0);
	return 0;
}