Submission #1042970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042970		Sharky	Quality Of Living (IOI10_quality)	C++17	100 / 100	1134 ms	140496 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 1, r = R * C;
	while (l < r) {
		int mid = (l + r) / 2;
		bool ok = 0;
		vector<vector<int>> ps(R, vector<int> (C, 0));
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (i == 0 && j == 0) ps[i][j] = (Q[i][j] <= mid);
				else if (i == 0) ps[i][j] = ps[i][j - 1] + (Q[i][j] <= mid);
				else if (j == 0) ps[i][j] = ps[i - 1][j] + (Q[i][j] <= mid);
				else ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + (Q[i][j] <= mid);
			}
		}
		for (int i = H - 1; i < R; i++) {
			for (int j = W - 1; j < C; j++) {
				int sum = ps[i][j];
				if (i >= H) sum -= ps[i - H][j];
				if (j >= W) sum -= ps[i][j - W];
				if (i >= H && j >= W) sum += ps[i - H][j - W];
				if (sum >= (H * W + 1) / 2) {
					ok = 1;
					break;
				}
			}
			if (ok) break;
		}
		if (ok) r = mid;
		else l = mid + 1;
	}
	return l;
}

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