Mooncrater's blog

How is the 256MB memory divided amongst the stack and the heap for questions and more questions
By Mooncrater, history, 5 years ago, In English

I recently solved 743-D. This required me to create an adjacency list of size 2e5. So, I'd to create a vector of vectors, i.e vector<vector<int>>. If one checks the size of a vector<int> variable, then we'll get 24 bytes. So, $$$4.8 \times 10^6$$$ bytes = 4.8MB. The question clearly mentions that we're given a total of 256 MBs. So the problem here might be that the stack size is smaller than 4.8 MB.

  1. So, What is the stack size, and the heap size?

My solution, that used this approach got an MLE (memory limit exceeded).

So, I decided to use the heap memory instead, (by using the new keyword). Here is the submission. The code is obviously harder and less clear. So,

  1. Are there other ways to avoid heap usage? Is there something obvious that I'm missing?

  2. Are there some easier and obvious ways to use the heap memory?

Any help regarding this is appreciated!

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here I added 3 characters to your MLE solution and got AC using ~32MB.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Facepalm. So, I was basically copying al the whole time. Ughh.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So, there is no such case when one has to use heap memory instead of the stack memory? (Not including dynamic memory allocation). And is the 256MB all stack memory?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I usually assume the stack size is set to the problem's memory limit which is true in ICPC.

      → Reply