ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1146. Maximum Sum

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
Posted by Mahilewets 28 Jun 2017 13:18
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
Posted by Mahilewets 28 Jun 2017 13:20
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.