记录编号	322293	评测结果	AAAAAAAAAAAAAAA
题目名称	乐曲主题	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2016-10-14 21:33:47	内存使用	0.38 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ULL unsigned long long
using namespace std;
const int maxn=5010;
const ULL T=173ull;
void init();
ULL hash(int,int);
ULL h[maxn],pw[maxn],tmp;
int n,a[maxn],L,R,M;
bool ok;
map<ULL,int>id;
int main(){
#define MINE
#ifdef MINE
	freopen("theme.in","r",stdin);
	freopen("theme.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=n;i;i--)a[i]-=a[i-1];
	init();
	L=4;R=n;
	while(L<=R){
		M=(L+R)>>1;
		ok=false;
		id.clear();
		for(int i=1;i+M-1<=n;i++){
			tmp=hash(i,M);
			if(id.count(tmp)){
				if(id[tmp]<i-M){
					ok=true;
					break;
				}
			}
			else id[tmp]=i;
		}
		if(ok)L=M+1;
		else R=M-1;
	}
	if(L<5)L=0;
	printf("%d",L);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
inline void init(){
	for(int i=n;i;i--)h[i]=h[i+1]*T+(a[i]+1);
	pw[0]=1ull;
	for(int i=1;i<=n;i++)pw[i]=pw[i-1]*T;
}
inline ULL hash(int x,int l){return h[x]-h[x+l]*pw[l];}
/*
30
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
82 78 74 70 66 67 64 60 65 80
Answer:
9
*/