Submission #1051585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051585		anton	Fibonacci representations (CEOI18_fib)	C++17	0 / 100	29 ms	33776 KiB

fib

#include<bits/stdc++.h>

using namespace std;
#define int long long
int N;
const int MOD = 1e9+7;
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 = 100000;
signed main(){
    cin>>N;
    
    vector<int> a(N);

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

    calc_fib(16);


    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]+dp[cur_s][cur_fib-1])%MOD;
                }
                if(cur_fib>0 && cur_s>=fib[cur_fib-1]){
                    dp[cur_s][cur_fib] = (dp[cur_s][cur_fib]+dp[cur_s-fib[cur_fib-1]][cur_fib-1])%MOD;
                }
            }
        }
    }

    int pref= 0;


    for(int i = 0; i<N; i++){
        pref += fib[a[i]-1];
        //cout<<pref<<endl;
        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