oj.uz

Submission #1051591

# Submission time Handle Problem Language Result Execution time Memory
1051591 2024-08-10T08:27:39 Z anton Fibonacci representations (CEOI18_fib) C++17
5 / 100
 40 ms 49748 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;
const int K= 25;
signed main(){
    cin>>N;
    
    vector<int> a(N);

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

    calc_fib(K);


    vector<vector<int>> dp(MAX_S, vector<int>(K+1, 0));
    for(int cur_s= 0; cur_s<MAX_S; cur_s++){
        for(int cur_fib= 0; cur_fib<=K;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][K]<<endl;
    }
    
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24664 KB Output is correct
2 Correct 26 ms 24692 KB Output is correct
3 Correct 29 ms 24668 KB Output is correct
4 Correct 29 ms 24668 KB Output is correct
5 Correct 27 ms 24668 KB Output is correct
6 Correct 26 ms 24668 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24664 KB Output is correct
2 Correct 26 ms 24692 KB Output is correct
3 Correct 29 ms 24668 KB Output is correct
4 Correct 29 ms 24668 KB Output is correct
5 Correct 27 ms 24668 KB Output is correct
6 Correct 26 ms 24668 KB Output is correct
7 Correct 26 ms 24668 KB Output is correct
8 Runtime error 40 ms 49720 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24664 KB Output is correct
2 Correct 26 ms 24692 KB Output is correct
3 Correct 29 ms 24668 KB Output is correct
4 Correct 29 ms 24668 KB Output is correct
5 Correct 27 ms 24668 KB Output is correct
6 Correct 26 ms 24668 KB Output is correct
7 Correct 26 ms 24668 KB Output is correct
8 Runtime error 40 ms 49720 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 49488 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 26 ms 24664 KB Output is correct
2 Correct 26 ms 24692 KB Output is correct
3 Correct 29 ms 24668 KB Output is correct
4 Correct 29 ms 24668 KB Output is correct
5 Correct 27 ms 24668 KB Output is correct
6 Correct 26 ms 24668 KB Output is correct
7 Correct 26 ms 24668 KB Output is correct
8 Runtime error 40 ms 49720 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -