Codeforces--633D--Fibonacci-ish （map+去重）（twice）



Fibonacci-ish

Time Limit: 3000MS

Memory Limit: 524288KB

64bit IO Format: %I64d & %I64u

Submit Status

Description

Yash has recently learnt about the Fibonacci sequence and is very excited about it. He calls a sequence Fibonacci-ish if

1. the sequence consists of at least two elements
2. f₀ and f₁ are arbitrary
3. f_n + 2 = f_n + 1 + f_n for all n ≥ 0.

You are given some sequence of integers a₁, a₂, ..., a_n. Your task is rearrange elements of this sequence in such a way that its longest possible prefix is Fibonacci-ish sequence.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 1000) — the length of the sequence a_i.

The second line contains n integers a₁, a₂, ..., a_n (|a_i| ≤ 10⁹).

Output

Print the length of the longest possible Fibonacci-ish prefix of the given sequence after rearrangement.

Sample Input

Input

3
1 2 -1

Output

3

Input

5
28 35 7 14 21

Output

4

Sample Output

Hint

In the first sample, if we rearrange elements of the sequence as  - 1, 2, 1, the whole sequence a_i would be Fibonacci-ish.

In the second sample, the optimal way to rearrange elements is , , , , 28.

Source

Manthan, Codefest 16

我去，以前做过的，就记得是dfs，但是忘记要用map跟去重了，真是人老了，记性不行咯

#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
int num[1010];
map<int, int>fp;
int DFS(int a, int b)
{
	int ans = 0;
	if (fp[a + b])
	{
		fp[a + b]--;
		ans=DFS(b, a + b)+1;
		fp[a + b]++;
	}
	return ans;
}
int main()
{
	int n;
	while (cin >> n)
	{
		memset(num, 0, sizeof(num));
		fp.clear();
		for (int i = 0; i < n; i++)
			cin >> num[i], fp[num[i]]++;
		sort(num, num + n);
		int ans = 0;
		int N = unique(num, num + n)-num;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (i == j&&fp[num[i]] == 1) continue;
				fp[num[i]]--, fp[num[j]]--;
				ans = max(ans, DFS(num[i], num[j]) + 2);
				fp[num[i]]++, fp[num[j]]++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}