Submission #405405

#	Time	Username	Problem	Language	Result	Execution time	Memory
405405		ollel	Fibonacci representations (CEOI18_fib)	C++14	5 / 100	4058 ms	344 KiB

fib

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

int n;
const int maxf = 20;
const int p2f = 1048576;

vi f(maxf);
void getf() {
  f[0] = 1; f[1] = 2;
  rep(i,2,maxf) f[i] = f[i - 2] + f[i - 1];
}

ll ways(int x) {
  int ways = 0;
  rep(ss, 0, p2f) {
    ll s = 0;
    rep(i,0,maxf) {
      if (ss & (1<<i)) s += f[i];
    }
    if (s == x) ways++;
  }
  return ways;
}

int main()
{
  cin >> n;
  getf();
  int des = 0;
  rep(i,0,n) {
    int x; cin >> x; des += f[x-1];
    cout << ways(des) << endl;
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35