Help me in solving Fibonacci Sums

help
1

https://szkopul.edu.pl/problemset/problem/98e_K-Vvcg5TnMG4-hXTNsFG/site/?key=statement

Here’s my try :

#include <bits/stdc++.h>
#define int long long
#define vi vector<int>
using namespace std;

void setIO() {
  cin.tie(0)->ios_base::sync_with_stdio(0);
}

void solve() {
  vi dp(1000000001);
  dp[1] = 1;
  dp[2] = 2;
  for(int i = 3;i <= 1000000000;++i) dp[i] = dp[i-1]+dp[i-2];
  int m,n,x = 0,y;
  cin >> m;
  for(int i = 1;i <= m;++i) {
    cin >> y;
    x += y*dp[i];
  }
  cin >> n;
  for(int i = 1;i <= n;++i) {
    cin >> y;
    x += y*dp[i];
  }
  auto it = upper_bound(dp.begin(),dp.end(),x);
  int k = distance(dp.begin(),it);
  vi res(k);
  for(int i = k-1;i >= 0;--i) {
    if(dp[i] > x) continue;
    x -= dp[i];
    res[i] = 1;
  }
  cout << k;
  for(auto &x : res) cout << ' ' << x;
}

int32_t main() {
  setIO();
  solve();
  return 0;
}

I don’t know why am I getting segmentation fault(run time error) but i m not going out of the bound anywhere or anything wrong :thinking::sweat_smile:

2

@angelash2024
U can’t create dp of that much size.
and also can’t run loop till 10^9 .
U have to optimize your code.

1 Like
3

But how sir if I don’t precompute every time i ve to recursively get fibonacci numbers then ?

4

@angelash2024
but u are taking that much memory(till 10^9*4 bytes) which is not possible .

1 Like
5

Yeah but then how to optimise it ? :thinking:

6

@angelash2024
In the problem link u have mentioned , the maximum value of n is 10^6 so u have take that much size or u have also use two values concept to reduce more size .

1 Like
7

Well thanks and sorry but either way my bruteforce approach is not gonna work as n goes upto 1e6 and no way 1e6th Fibonacci number cannot be retrieved or stored so I m seeking for some other optimal/greedy way to do it