memory usage

[MattC98]

I have the following problem : Given an NxM matrix (elements 0 at the beginning),you read N , M , q and T and T lines as following : reading 5 integers l1,c1, l2,c2 and x, all elements from submatrix created by these two points increasca by x, l1 c1 is the up right corner and l2 c2 down left. After the matrix is created find the biggest area of elements which are bigger than a given integer q. it doesnt have to have any specifif shape just to be neighbor elements.
ex :
Input :
8 7 5
7
1 1 3 6 1
4 2 5 7 2
2 3 4 7 3
1 2 4 3 3
5 1 6 3 4
5 5 7 6 2
6 4 8 7 3
output : 10 (the max area)
this is my first solution which got 55/100 points for memory limit exceeded, I have 20mb and :
2 ≤ N, M ≤ 1000
1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ M
1 ≤ q ≤ 1000
1 ≤ Q ≤ 10000
1 ≤ T ≤ 50000
first solution (55/100 for memory limit exceeded) :
https://pastebin.com/t9YQVQGL
and this is my second solution which got 100/100 , why does the first solution use so much more memory ?
second solution : https://pastebin.com/iuwvQJBn

[tpb]

Post the link to the online question.

Presumably l1,c1 is the upper-left and l2,c2 is the lower-right.

I haven't looked at your code yet, but from your other question (which you should maybe delete) it uses a fill algorithm. Assuming it's recursive, then it uses so much memory due to the stack space used by the recursion. Although if you coded it wrong it might use a lot more space than it needs to.

[MattC98]

yes l1, c1 is upper left and l2 c2 in lower right, im not english and the quest is not in english, but i think you answered my question : my first solution used fill and got memory limit exceeded and then i switched to a queue and got 100/100, i didnt know recursion uses a lot of memory, thanks

[dhayden]

It looks to me like there is about 4.25MB of RAM used by variables. 4MB is mat, 128k in InputReader::buff and 126k in um

So where is the problem? I suspect it's in ump(). In the first solution, ump() is recursive, so the stack contains the parameters, local variables and return address of each recursive call. In the second version, you use a queue and you pop the queue before adding new values to its end. It's possible that simply moving the pop() to the end of the while loop will make the second solution as bad as the first.

By the way, InputReader is needlessly complex and actually hurts performance. Just use setvbuf() to set fin's buffer to buff. As coded now, fin buffers the data, and the InputReader buffers it again.