CFR 633 D. Fibonacci-ish ( Ad hoc )

Problem - D - Codeforces
It is easy to realize that once the first two elements are determined, the rest in the Fibonacci sequence are determined as well. Another important property is that Fibonacci sequence expands exponentially, and given that restriction abs( a[ i ] ) <= 1e9 exists, a little rough overestimation can lead us to that the maximum length of a valid sequence will not exceed 100. However, note that, if the first two elements are 0, there will be an exception where it is valid to put as many 0 as we want.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;

int n;
int a[ MAXN ];
map<int, int> occ;

void init(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d", &a[ i ]);
        ++occ[ a[ i ] ];
    }
}

int getMaxLength(int f0, int f1){
    map<int, int> used;
    ++used[ f0 ], ++used[ f1 ];
    int res = 2;
    while( true ){
        int f2 = f0 + f1;
        if( used[ f2 ] + 1 > occ[ f2 ] ) break;
        ++used[ f2 ];
        ++res;
        f0 = f1, f1 = f2;
    }
    return res;
}

typedef pair<int, int> pii;
void solve(){
    set<pii> vis;
    int best = occ[ 0 ] >= 2 ? occ[ 0 ] : 0;;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j) if( i != j ){
            if( a[ i ] == 0 && a[ j ] == 0 ) continue;
            if( vis.count( pii( a[ i ], a[ j ] ) ) ) continue;
            vis.insert( pii( a[ i ], a[ j ] ) );
            best = max<int>( best, getMaxLength( a[ i ], a[ j ] ) );
        }
    }
    printf("%d\n", best);
}

int main(){
    init();
    solve();
    return 0;
}