Submission #240141

#	Time	Username	Problem	Language	Result	Execution time	Memory
240141		staniewzki	Quality Of Living (IOI10_quality)	C++17	100 / 100	2332 ms	71256 KiB

quality

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#include "quality.h"

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	auto check = [&](int m) {
		vector<vector<int>> pref(R + 1, vector<int>(C + 1));
		FOR(i, 0, R - 1) FOR(j, 0, C - 1) {
			int v = (Q[i][j] <= m ? +1 : -1);
			pref[i + 1][j + 1] = pref[i + 1][j] + pref[i][j + 1] - pref[i][j] + v;
		}

		FOR(i, H, R) FOR(j, W, C) {
			if(pref[i][j] - pref[i - H][j] - pref[i][j - W] + pref[i - H][j - W] >= 1)
				return true;
		}
		return false;
	};

	int l = 1, r = R * C;
	while(l < r) {
		int m = (l + r) / 2;
		if(check(m))
			r = m;
		else
			l = m + 1;
	}
	return l;
}

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