1718B - Fibonacci Strings - CodeForces Solution

/*
    Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;

long long k , fib [300] , did [300];

int main()
{
    fib [0] = 1 , fib [1] = 1;
    for ( int i = 2 ; i <= 80 ; i ++ ) fib [i] = fib [ i - 1 ] + fib [ i - 2 ];

    //for ( int i = 0 ; i <= 50 ; i ++ ) cout << ' ' << i << ' ' << fib [i] << endl;

    int T;
    cin >> T;
    while ( T -- )
    {
        cin >> k;
        vector < pair < long long , int > > v;
        long long sum = 0;
        for ( int i = 0 ; i < k ; i ++ )
        {
            int x;
            cin >> x;
            sum += x;
            v . push_back ( { x , 0 } );
        }

        long long lim = 0 , summ = 0;
        for ( int i = 0 ; i < 80 ; i ++ )
        {
            summ += fib [i];
            lim = i;
            if ( summ >= sum ) break;
        }
        if ( summ != sum )
        {
            cout << "NO" << endl;
            continue;
        }

        int f = 0;
        for ( int i = lim ; i >= 0 ; i -- )
        {
            sort ( v . rbegin () , v . rend () );
            for ( int j = 0 ; j < k ; j ++ )
            {
                if ( v [j] . second ) continue;
                if ( v [j] . first >= fib [i] )
                {
                    v [j] . first -= fib [i];
                    for ( int z = 0 ; z < k ; z ++ ) v [z] . second = 0;
                    v [j] . second = 1;
                    break;
                }
            }
        }
        for ( int i = 0 ; i < k ; i ++ )
        {
            if ( v [i] . first ) f = 1;
        }
        if ( f ) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
}