I am unable to understand why declaring an array dp[71][1<<20] results in MEMORY LIMIT EXCEEDED in the code. As far as the problem definition is concerned I only need 19 bits (there are 19 prime numbers less than 70) hence the problem can be solved by using array of size dp[71][1<<19]. Using the latter I have indeed got AC but I don't know why my code is taking too much memory in general.

Link to the problem

Here goes my code:

include<bits/stdc++.h>

using namespace std;

define fr first

define se second

define ll long long

define loop(i,a,b) for(ll i=a;i<b;i++)

define rloop(i,a,b) for(ll i=a;i>b;i--)

define vi vector

define vvi vector

define pb push_back

define ppb pop_back

define pii pair<int,int>

define vll vector

define sz(a) int(a.size())

define last(x) x.end()

define beg(x) x.begin()

define all(x) begin(x),end(x)

define inTree(m,n) m.find(n)!=m.end()

define inp(a,n) loop(i,0,n) cin>>a[i]

define divs(n,m) ((m!=0)&&(n%m==0))

define Sum(ctnr) accumulate(begin(ctnr),end(ctnr),0ll)

define iter(ctnr,it) for(auto it=ctnr.begin();it!=ctnr.end();it++)

define tr(ctnr,x) for(auto &x:ctnr)

define print(ctnr) tr(ctnr,x){ cout<<x<<" "; } cout<<endl

define printarr(a,n) loop(i,0,n){ cout<<a[i]<<" "; }cout<<endl

define br '\n'

template<typename ...Arg> void read(Arg& ...arg){ ((cin>>arg),...); }

void write(){ cout<<'\n'; } template<typename Arg1,typename ...ArgN> void write(Arg1& arg1,ArgN&...argN){ cout<<arg1<<" ";write(argN...); }

const int mod1=1e9+7; const int mod2=998244353; const int N=5e6+5; //Do not modify the value! const ll inf=LLONG_MAX; const double PI=3.14159265358979311600;

int mask[71],dp[71][1<<20];// Here lies the problem!!! int prime[19]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};

void computeMasks() { int binary,num,cnt; mask[0]=0; loop(i,1,71) { binary=0; loop(j,0,19) { cnt=0; num=i; while(num%prime[j]==0) { cnt++; num=num/prime[j]; } if(cnt%2) binary+=(1<<j); } mask[i]=binary; //cerr<<i<<" "; } //cerr<<br; }

ll binaryExponentiate(int x,int exp) { if(exp==0) { return 1; } ll val=binaryExponentiate(x,exp/2); val=(val*val)%mod1; if(exp%2) val=(val*x)%mod1; return val; } void solve() { //Declare your variables here.Avoid names of variables that are names of library functions int n,lim,x,maxx,ans,temp; ll oddselect,evenselect,term; unordered_map<int,int> m;

cin>>n;
maxx=0;
loop(i,0,n)
{
    cin>>x;
    m[x]++;
    maxx=max(maxx,x);
}
lim=(1<<19);
loop(i,0,maxx+1)
{
    loop(j,0,lim)
    {
       dp[i][j]=0;
    }
}    
computeMasks();
dp[0][0]=1;//If no elements are chosen and the required mask is 0 then null set is considered
loop(i,0,maxx)
{
    temp=binaryExponentiate(2,m[i+1]-1);
    oddselect=(m[i+1]>=1)?temp:0;
    evenselect=(m[i+1]>=1)?temp:1;
    loop(j,0,lim)
    {
       dp[i+1][j^mask[i+1]] = (dp[i+1][j^mask[i+1]] + (oddselect*dp[i][j])%mod1)%mod1;
       dp[i+1][j] = (dp[i+1][j] + (evenselect*dp[i][j])%mod1)%mod1;
    }

}
cout<<(dp[maxx][0]-1)<<br;

}

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t=1; //cin>>t; while(t--) solve(); }

Since I am posting for the first time I beg pardon for the ill formatting!