UVA – 10667 – Largest Block

#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <string>
#include <string.h>
#define FOR(ii, i0, in) for((ii)=(i0); (ii)<(in); (ii)++)
#define FOR2d(ii, jj, i0, j0, in, jn) FOR(ii, i0, in) FOR(jj, j0, jn)

using namespace std;

int main() {
	int i, j, k, T, N, B, i0, j0, in, jn;
	cin >> T;
	while (T-- && (cin>> N >> B)) {
		int a[N][N], MAX=0;
		memset(a, 0, sizeof a);

		while(B-- && (cin >> i0 >> j0 >> in >> jn) )
			FOR2d(i, j, i0-1, j0-1, in, jn)	a[i][j] =1;

		FOR2d(i, j, 0, 0, N, N)
			a[i][j] = (i && !a[i][j]) ? a[i - 1][j] + 1 : !a[i][j];

		FOR2d(i, j, 0, 0, N, N){
			int count = 1;
			for (k = j + 1; k  < N && a[i][j] <= a[i][k]; k++)	count++;
			for (k = j - 1; k >= 0 && a[i][j] <= a[i][k]; k--)	count++;
			MAX = max(count*a[i][j], MAX);
		}
		cout << MAX << endl;
	}
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: