10074 - Take the Land

[aybek]

Correct your output code to printf("%d\n", maxSubRectz);
and you have errors in your code.

[jishnu1]

@aybek
Sorry for the late reply.

I have tried printing that way too but i still receive a WA. I have updated the code. It compiles without errors (g++ compiler) and runs well on several test cases i provide on my computer. So if there are any errors pls be kind and notify them.
Thankx

[aybek]

jishnu1, I don't know what test case will break your solution, I can give you my code of solution,
and you might generate outputs from it and compare them with your solution outs.

Code: Select all

#include <iostream>
using namespace std;

int M, N;
int a[ 101 ][ 101 ];
int s[ 101 ][ 101 ];

void count_s() {
	int i, j;
	s[1][1] = a[1][1];

	for ( i = 2; i <= M; ++i )
		s[i][1] = s[i-1][1] + a[i][1];

	for ( j = 2; j <= N; ++j )
		s[1][j] = s[1][j-1] + a[1][j];

	for ( i = 2; i <= M; ++i )
		for ( j = 2; j <= N; ++j )
			s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j];
}

int main() {
	int i, j, x1, y1, x2, y2, max_area;
	for ( ;; ) {

		cin >> M >> N;
		if ( !M && !N ) break;

		max_area = 0;
		for ( i = 1; i <= M; ++i )
			for ( j = 1; j <= N; ++j )
				cin >> a[i][j];

		count_s();

		for ( x1 = 1; x1 <= M; ++x1 )
		for ( y1 = 1; y1 <= N; ++y1 )
			for ( x2 = x1; x2 <= M; ++x2 )
			for ( y2 = y1; y2 <= N; ++y2 )
				if ( (s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]) == 0 ) {
					max_area = max( (x2-x1+1)*(y2-y1+1), max_area );
				}

		cout << max_area << endl;
	}

	return 0;
}

[brianfry713]

jishnu1, change line 24 to:
if (i > 0) { A[j] += A[j] ; B[j] += B[i-1][j]; }
And line 30 to:
if (j > 0) { A[j] += A[j-1] ; B[j] += B[j-1]; }
And line 36 to:
if (i > 0 && j > 0) { A[j] = A[j] - A[i-1][j-1] ; B[j] = B[i][j] - B[i-1][j-1]; }

[jishnu1]

@brianfry713
Thankx, I finally got Accepted , but i did not quite understand the logic behind this , in a conditional statement like if isnt it true that u can put the assignment operations on one line if possible ?

if this is not the case isn't the judge supposed to report compilation error, and if my algorithm was coded the wrong way how was it able to pass several test cases?

My question is :

why:

Code: Select all

 if (i > 0) {A[i][j] += A[i - 1][j] ; B[i][j] += B[i-1][j];}

instead of this :

Code: Select all

 if (i > 0) A[i][j] += A[i - 1][j] ; B[i][j] += B[i-1][j];

[brianfry713]

No those code blocks are not equivalent. C is flexible with whitespace, it doesn't matter if the statements are on one line or not.

Code: Select all

if(cond)
  statement1; statement2;

is the same as:

Code: Select all

if(cond)
  statement1;
statement2;

You could use a , instead of ; if you wanted to write them without braces.

Code: Select all

if(cond)
  statement1, statement2;

is the same as:

Code: Select all

if(cond) {
  statement1;
  statement2;
}

You should change your coding style with whitespace, as it makes it more clear.

[asrajmane193]

hello. i keep getting wrong answer. I tried many random testcases and compared my outputs with the ones on udebug. they are equal. my code is here - http://ideone.com/dOLTFy

I have applied 1D maximum sum on a matrix. For every window of rows I try to find the starting and ending column.

For finding the window of columns, I save the starting and ending column indices which give me the maximum sum on the temporary array.

This runs is O(n^3)