MAP vs Arrays!

help
, ,
1

Hello TO THE VISITORS!!!
PROBLEM ARISES IN THISSSS
I want to ask why long long dp[10000000000] is wrong as they have mentioned 1e9.
But as soon as i change it to map<long long,long long> it starts working but WHY

#include <bits/stdc++.h>
using namespace std;
long long dp[1000000000];
long long solve(long long n){
    if(n<=10){
        return n;
    }
    
    if(dp[n]!=0){
        return dp[n];
    }
    dp[n] = max(n,solve((n/2))+solve((n/3))+solve((n/4)));
    return dp[n];



}


int main(){
    long long t;
    while(cin>>t){
        cout<<solve(t)<<"\n";
    }


}
2

long long dp[1000000000];

The size of this array is 8GB. And it exceeds the memory limit.

2 Likes
3

Why not map

4

Because std::map starts with essentially zero size and grows only when you add data into it. Its memory footprint is proportional to the number of unique indexes that had been actually accessed. It works great if you have big jumps between indexes or “holes” in your data.

But std::map needs more storage space per element and is slower to access compared to an ordinary array. So if you need to store, let’s say, 10000 elements with consecutive indexes and all of them are guaranteed to be accessed, then an ordinary array or std::vector will be more efficient.

2 Likes
5

Thanks!