Submission #1051557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051557		anton	Fibonacci representations (CEOI18_fib)	C++17	0 / 100	3 ms	5724 KiB

fib

#include<bits/stdc++.h>

using namespace std;
#define int long long
int N;

vector<int> fib;

void calc_fib(int n){
    int cur=1;
    int prev= 1;

    for(int i = 0; i<n;i++){
        fib.push_back(cur);
        int next = cur+prev;
        prev = cur;
        cur = next;
    
    }
}
const int MAX_S = 16000;
signed main(){
    cin>>N;
    
    vector<int> a(N);

    for(int i = 0; i<N; i++){
        cin>>a[i];
    }

    calc_fib(15);


    vector<vector<int>> dp(MAX_S, vector<int>(16, 0));
    for(int cur_s= 0; cur_s<MAX_S; cur_s++){
        for(int cur_fib= 0; cur_fib<=15;cur_fib++){
            if(cur_s == 0 && cur_fib==0){
                dp[0][0]=1;
            }
            else{
                if(cur_fib>0){
                    dp[cur_s][cur_fib] += dp[cur_s][cur_fib-1];
                }
                if(cur_fib>0 && cur_s>=fib[cur_fib-1]){
                    dp[cur_s][cur_fib] += dp[cur_s-fib[cur_fib-1]][cur_fib-1];
                }
            }
        }
    }

    int pref= 0;


    for(int i = 0; i<N; i++){
        pref += fib[a[i]-1];
        cout<<dp[pref][15]<<endl;
    }
    
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35