oj.uz

Submission #1051585

# Submission time Handle Problem Language Result Execution time Memory
1051585 2024-08-10T08:26:29 Z anton Fibonacci representations (CEOI18_fib) C++17
0 / 100
 29 ms 33776 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16732 KB Output is correct
2 Incorrect 17 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16732 KB Output is correct
2 Incorrect 17 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 16728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16732 KB Output is correct
2 Incorrect 17 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 33776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16732 KB Output is correct
2 Incorrect 17 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -