Submission #1046543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046543		EntityPlantt	Quality Of Living (IOI10_quality)	C++17	100 / 100	1122 ms	140052 KiB

quality

#include "quality.h"
const int N = 3001;
typedef const int& cir;
int pref[N + 1][N + 1];
bool ok(cir R, cir C, cir H, cir W, int Q[N][N], cir X) {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			pref[i][j] = pref[i][j - 1] + pref[i - 1][j] - pref[i - 1][j - 1] + (Q[i - 1][j - 1] <= X ? 1 : -1);
			if (i >= H && j >= W && pref[i][j] - pref[i - H][j] - pref[i][j - W] + pref[i - H][j - W] > 0) return true;
		}
	}
	return false;
}
int rectangle(int R, int C, int H, int W, int Q[N][N]) {
	int l = 1, r = R * C, ans = r;
	while (l <= r) {
		int m = l + r >> 1;
		if (ok(R, C, H, W, Q, m)) {
			ans = m;
			r = m - 1;
		}
		else l = m + 1;
	}
	return ans;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:17:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |   int m = l + r >> 1;
      |           ~~^~~

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