Submission #550987

#	Time	Username	Problem	Language	Result	Execution time	Memory
550987		Jomnoi	Quality Of Living (IOI10_quality)	C++17	100 / 100	2543 ms	140408 KiB

quality

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

bool solve(int mid, int R, int C, int H, int W, int a[3001][3001]) {
	vector <vector <int>> qs(3001, vector <int> (3001, 0));
	for(int i = 1; i <= R; i++) {
		for(int j = 1; j <= C; j++) {
			qs[i][j] += qs[i - 1][j] + qs[i][j - 1] - qs[i - 1][j - 1];
			if(a[i - 1][j - 1] < mid) {
				qs[i][j]--;
			}
			else if(a[i - 1][j - 1] > mid) {
				qs[i][j]++;
			}
		}
	}

	for(int i = H; i <= R; i++) {
		for(int j = W; j <= C; j++) {
			if(qs[i][j] - qs[i - H][j] - qs[i][j - W] + qs[i - H][j - W] <= 0) {
				return true;
			}
		}
	}
	return false;
}

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;

		if(solve(mid, R, C, H, W, Q) == true) {
			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