Submission #758615

#	Time	Username	Problem	Language	Result	Execution time	Memory
758615		SanguineChameleon	Quality Of Living (IOI10_quality)	C++17	100 / 100	1893 ms	140388 KiB

quality

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

int n, m, h, w;
int (*a)[3001];
int pref[3020][3020];

int get(int lx, int ly, int rx, int ry) {
	return pref[rx][ry] - pref[rx][ly - 1] - pref[lx - 1][ry] + pref[lx - 1][ly - 1];
}

bool check(int x) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			pref[i + 1][j + 1] = (a[i][j] <= x ? 1 : -1);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			pref[i][j] += pref[i][j - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			pref[i][j] += pref[i - 1][j];
		}
	}
	for (int i = h; i <= n; i++) {
		for (int j = w; j <= m; j++) {
			if (get(i - h + 1, j - w + 1, i, j) > 0) {
				return true;
			}
		}
	}
	return false;
}

int rectangle(int _n, int _m, int _h, int _w, int _a[3001][3001]) {
	n = _n;
	m = _m;
	h = _h;
	w = _w;
	a = _a;
	int res = -1;
	int lt = 1;
	int rt = n * m;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		if (check(mt)) {
			res = mt;
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	return res;
}

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