Meteoriti

#include <cstdio>
#include <deque>
using namespace std;

const char INFILE[] = "meteoriti.in";
const char OUTFILE[] = "meteoriti.out";

const int NMAX = 2 * 1000 + 2;
const int RMAX = 100 * 1000 + 2;

const int DIR[4][4] = {
	{-1, 0, 1, 0},
	{0, 1, 0, -1}
};

int n, m, maxx, cnt, sol1, sol2;
int mat[NMAX][NMAX];
deque< pair<int, int> > deq;

void GetMax()
{
	for (int j, i = 1; i <= n; ++i)
		for (j = 1; j <= m; ++j) {
			mat[i][j] += mat[i][j - 1];
			if (mat[i][j] > maxx)
				maxx = mat[i][j];
		}

	for (int j, i = 1; i <= m; ++i)
		for (j = 1; j <= n; ++j) {
			mat[j][i] += mat[j - 1][i];
			if (mat[j][i] > maxx)
				maxx = mat[j][i];
		}
}

inline void FillMat(int row, int col)
{
	int new_row, new_col;
	deq.push_back(make_pair(row, col));
	mat[row][col] = -maxx;

	while (!deq.empty()) {
		if (++cnt > sol1)
			sol1 = cnt;

		row = deq.front().first;
		col = deq.front().second;
	    for (int i = 0; i < 4; ++i) {
			new_row = row + DIR[0][i];
			new_col = col + DIR[1][i];
			if (new_row && new_col && new_row <= n && new_col <= m)
			if (mat[new_row][new_col] == maxx) {
				mat[new_row][new_col] = -maxx;
				deq.push_back(make_pair(new_row, new_col));
			}
		}
		deq.pop_front();
	}
}

int main()
{
	freopen(INFILE, "r", stdin);
	freopen(OUTFILE, "w", stdout);

	int r, x1, y1,x2, y2, c;
	scanf("%d%d", &n, &m);
	for (scanf("%d", &r); r; --r) {
		scanf("%d%d", &x1, &y1);
		scanf("%d%d", &x2, &y2);
		scanf("%d", &c);
		mat[x1][y1] += c;
		mat[x1][y2 + 1] -= c;
		mat[x2 + 1][y1] -= c;
		mat[x2 + 1][y2 + 1] += c;
	}

	GetMax();

	for (int j, i = 1; i <= n; ++i)
		for (j = 1; j <= m; ++j)
			if (mat[i][j] == maxx) {
				cnt = 0;
				FillMat(i, j);
			}
			else if (!mat[i][j])
				++sol2;

	printf("%d %d", sol1, sol2);

	return 0;
}