## 10074 - Take the Land

Moderator: Board moderators

aybek
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

### Re: uva 10074: Take the Land WA

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

jishnu1
New poster
Posts: 4
Joined: Sat Jun 21, 2014 1:24 am

### Re: uva 10074: Take the Land WA

@aybek

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
New poster
Posts: 19
Joined: Fri Jul 19, 2013 10:25 am
Contact:

### Re: uva 10074: Take the Land WA

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 = a;

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

for ( j = 2; j <= N; ++j )
s[j] = s[j-1] + a[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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: uva 10074: Take the Land WA

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]; }
Check input and AC output for thousands of problems on uDebug!

jishnu1
New poster
Posts: 4
Joined: Sat Jun 21, 2014 1:24 am

### Re: uva 10074: Take the Land WA

@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];}``

Code: Select all

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: uva 10074: Take the Land WA

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.
Check input and AC output for thousands of problems on uDebug!

asrajmane193
New poster
Posts: 5
Joined: Tue May 26, 2015 9:55 am

### Re: 10074 - Take the Land

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)