Submission #532414

#	Time	Username	Problem	Language	Result	Execution time	Memory
532414		sliviu	Quality Of Living (IOI10_quality)	C++17	100 / 100	2237 ms	118584 KiB

quality

#include <bits/stdc++.h>

using namespace std;

int rectangle(int N, int M, int y, int x, int q[3001][3001]) {
	int left = 1, right = N * M;
	while (left < right) {
		int m = (left + right) / 2;
		auto ok = [&](int cost) {
			vector<vector<int>> s(N + 1, vector<int>(M + 1));
			for (int i = 1; i <= N; ++i)
				for (int j = 1; j <= M; ++j)
					s[i][j] = ((q[i - 1][j - 1] < cost) ? -1 : (q[i - 1][j - 1] == cost ? 0 : 1)) + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
			for (int i = 1; i <= N - y + 1; ++i)
				for (int j = 1; j <= M - x + 1; ++j) {
					int ii = i + y - 1, jj = j + x - 1;
					if (s[ii][jj] - s[i - 1][jj] - s[ii][j - 1] + s[i - 1][j - 1] <= 0)
						return 1;
				}
			return 0;
		};
		if (ok(m))
			right = m;
		else
			left = m + 1;
	}
	return left;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20