Submission #433907

#	Time	Username	Problem	Language	Result	Execution time	Memory
433907		KoD	Quality Of Living (IOI10_quality)	C++17	100 / 100	1662 ms	140044 KiB

quality

#include "quality.h"

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	static int sum[3001][3001] = {};
	int ok = R * C, ng = 0;
	while (ok - ng > 1) {
		const auto md = (ok + ng) / 2;
		for (int i = 0; i < R; ++i) {
			for (int j = 0; j < C; ++j) {
				sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + (Q[i][j] <= md);
			}
		}
		bool f = false;
		for (int i = H; !f and i <= R; ++i) {
			for (int j = W; !f and j <= C; ++j) {
				if (sum[i][j] - sum[i - H][j] - sum[i][j - W] + sum[i - H][j - W] > H * W / 2) {
					f = true;
				}
			}
		}
		if (f) {
			ok = md;
		} else {
			ng = md;
		}
	}
	return ok;
}

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