Submission #240139

#	Time	Username	Problem	Language	Result	Execution time	Memory
240139		staniewzki	Quality Of Living (IOI10_quality)	C++17	100 / 100	2491 ms	140544 KiB

quality

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#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));
		REP(i, R) REP(j, C) {
			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