oj.uz

Submission #128524

# Submission time Handle Problem Language Result Execution time Memory
128524 2019-07-11T05:49:34 Z 송준혁(#3162) Fibonacci representations (CEOI18_fib) C++14
15 / 100
 4000 ms 376 KB 
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M;
int A[110];
vector<int> V;
LL D1[110], D2[110];

int main(){
    scanf("%d", &N);
    for (int i=1; i<=N; i++) scanf("%d", &A[i]);
    D1[0] = 0, D2[0] = 1;
    for (int i=1; i<=N; i++){
        V.clear();
        for (int j=1; j<=i; j++) V.push_back(A[j]);
        V.push_back(0);
        sort(V.begin(), V.end());
        for (int k=1; k<=i+1; k++){
            for (int j=1; j<(int)V.size()-1; j++){
                if (V[j] == 1 && V[j+1] == 1) V[j+1]=2, V[j]=MOD;
                if (V[j]+1 == V[j+1]) V[j+1] = V[j+1]+1, V[j]=MOD;
            }
            sort(V.begin(), V.end());
            while (V.back() == MOD) V.pop_back();
        }
        for (int j=1; j<(int)V.size(); j++){
            D1[j] = D1[j-1] * ((V[j]-V[j-1])/2);
            D1[j] += D2[j-1] * ((V[j]-V[j-1]-1)/2);
            D2[j] = D1[j-1];
            if (V[j-1] < V[j]) D2[j] += D2[j-1];
            D1[j] %= MOD, D2[j] %= MOD;
        }
        printf("%lld\n", (D1[V.size()-1]+D2[V.size()-1])%MOD);
    }
    return 0;
}

Compilation message

fib.cpp: In function 'int main()':
fib.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
fib.cpp:14:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=N; i++) scanf("%d", &A[i]);
                              ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 20.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 252 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4091 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

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