This is WEIRD

Posted by

iOli 26 Jun 2017 17:05

My solution passes first 4 test cases and shows memory limit exceeded error at 5th test case. I have made a global 4D array 100*100*100*100 which keeps the result of the sum of a rectangle whose top left corner is x1,y1 and bottom right corner is x2,y2, 4d array mat[x1][y1][x2][y2] stores the sum of the numbers corresponding to that rectangle. Now if this big array were a reason behind memory limit exceeded error than it shouldn't have passed even the first test cases because i made global 4d array of maximum size by default. So what can be the reason?

#include <iostream>

using namespace std;

const int M = 107;

int mat[M][M][M][M];

int main() {

int n;

cin >> n;

int arr[n][n];

int ans = -1e9;

for (int i=0; i<n; i++)

for (int j=0; j<n; j++) {

cin >> arr[i][j];

mat[i][j][i][j] = arr[i][j];

if (arr[i][j] > ans) ans = arr[i][j];

}

for (int size = 2; size<=n*n; size++) {

for (int p=1; p<=size and p<=n; p++) {

int q = size/p;

if (p*q != size) continue;

for (int i=0; i<n-p+1; i++) {

for (int j=0; j<n-q+1; j++) {

int x1 = i, y1 = j;

int x2 = i+p-1, y2 = j+q-1;

if (x2-x1 > y2-y1) {

mat[x1][y1][x2][y2] = mat[x1][y1][x2-1][y2] + mat[x2][y1][x2][y2];

if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2];

}

else {

mat[x1][y1][x2][y2] = mat[x1][y1][x2][y2-1] + mat[x1][y2][x2][y2];

if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2];

}

}

}

}

}

cout << ans << endl;

}

*Edited by author 26.06.2017 17:06*

*Edited by author 26.06.2017 17:06*

*Edited by author 26.06.2017 17:07*

Re: This is WEIRD

Actually, if you don't access your global allocated memory, that memory don't counts.

I have noticed that when watching how my solutions are testing. When there is a global array of big size first few cases are low memory. And last test cases are high memory usage.

Re: This is WEIRD

You can find any simple task were you are to output some string. Allocate a HUGE buffer for that string. Then submit your solution. Then allocate a buffer just enough to hold your string and submit again. And you will see that memory usage is the SAME.