oj.uz

Submission #1051557

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

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Incorrect 2 ms 2908 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 3 ms 5724 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 2 ms 2908 KB Output is correct
2 Incorrect 2 ms 2908 KB Output isn't correct
3 Halted 0 ms 0 KB -