Why am I getting MLE (Memory Limit Exceeded) error in this problem

Problem link: https://codeforces.com/problemsets/acmsguru/problem/99999/123

// #include<bits/stdc++.h>
// #define f(a,b) for(int i=a;i<b;i++)
// #define dbg(x); cout<<"\n"<<#x<<": "<<x<<"\n";
#define ret return
using namespace std;
const int MAX=41;
int f[MAX]={0};
int fibo(int k){
	if(k==0)	ret 0;
	if(k==1||k==2)	ret (f[k]=1);
	if(f[k])	ret f[k];
	int m=(k&1)?(k+1)/2:k/2;
	ret f[k];
int sum(int k){
	ret fibo(k+2)-1;
int main(){ 
	// ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
	int k;
	ret 0; 

Most likely stack overflow…
Try writing an iterative solution

Well it’s very simple
Just tabulate first k numbers and sum them up afterwards

yeah that was naive approach

maybe using vector instead of static array will do

No difference.
Even in recursion this is normal
Use Fibonacci function till k and store them in an array
Then do summation of that.

int table[42];
int fib(int k){
      if(k==0 or k==1) //base conditions 
          return 1;
      if(table[k]!=0) return table[k];
      return table[k]=fib(k-1)+fib(k-2);

This is Fibonacci right?
Then just loop through 0 to k(inclusive) and add the values in a variable

1 Like

Don’t use a table, and no arrays. Don’t even need sum. Find the n+2th term and subtract 1
Use fib1=1
For i 3 to n+2



Yeah arrays obviously increase space.
I just wrote like that because he was using recursion to solve it

1 Like