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

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.

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.