__MR.WOLF's blog

Memory limit exceeded on test 8
By __MR.WOLF, history, 4 years ago, In English

Why i am getting memory limit exceeded

Problem 318A

include<bits/stdc++.h>

using namespace std;

int main() { long long n,j; cin>>n>>j;

vector<long long>v;

for(int i=1;i<=n;i+=2)
{
     v.push_back(i);
}

for(int j=2;j<=n;j+=2)
{
    v.push_back(j);
}

cout<<v[j-1]<<endl;

}

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
4 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

You are using O(n) space and n is of order 10^12. If you take 4 bytes for an integer, you'd be using 3725 TB of memory!!!

→ Reply
»
4 years ago, hide # |
← Rev. 3  
Vote: I like it +1 Vote: I do not like it

N is up to $$$10^{12}$$$. Even if you had infinite amount of memory, you still wouldn't be able to iterate over those $$$10^{12}$$$ elements. Or if you prefer some calculations: long long in most cases is 8 bytes. $$$(10^{12} * 8)$$$ bytes $$$= \bigg(\frac{10^{12} * 8} {2^{20}}\bigg)$$$ megabytes $$$\approx 7 * 10^6$$$ megabytes, but you have only $$$256$$$ megabytes avaliable.

→ Reply