Submission #706487

#	Time	Username	Problem	Language	Result	Execution time	Memory
706487		SamNguyen	Quality Of Living (IOI10_quality)	C++14	100 / 100	1578 ms	140332 KiB

quality

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

template <class Func>
int FIND_SMALLEST(int l, int r, Func f) {
	int res = r + 1;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (f(m)) res = m, r = m - 1;
		else l = m + 1;
	}
	return res;
}

template <class Func>
int FIND_LARGEST(int l, int r, Func f) {
	int res = l - 1;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (f(m)) res = m, l = m + 1;
		else r = m - 1;
	}
	return res;
}

template <class T1, class T2>
inline int minimise(T1 &x, T2 y) {
	if (x > y) { x = y; return true; }
	return false;
}

template <class T1, class T2>
inline int maximise(T1 &x, T2 y) {
	if (x < y) { x = y; return true; }
	return false;
}

int suf[3001][3001];
inline int GET_SUM(int x1, int y1, int x2, int y2) { 
	return suf[x1][y1] - suf[x2 + 1][y1] - suf[x1][y2 + 1] + suf[x2 + 1][y2 + 1];
}

int rectangle(int R, int C, int H, int W, int grid[3001][3001]) {
	int TARGET_SZ = H * W / 2 + 1;

	int res = FIND_SMALLEST(1, R * C, [&](int x) {
		memset(suf, 0, sizeof suf);
		for (int i = R - 1; i >= 0; i--)
		for (int j = C - 1; j >= 0; j--)
			suf[i][j] = (grid[i][j] <= x) + suf[i + 1][j] + suf[i][j + 1] - suf[i + 1][j + 1];

		/*
		cout << "x = " << x << endl;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++)
				cout << setw(3) << GET_SUM(i, j, i, j);
			cout << endl;
		}
		cout << "-------" << endl;
		*/

		for (int i = 0; i + H <= R; i++)
		for (int j = 0; j + W <= C; j++)
			if (GET_SUM(i, j, i + H - 1, j + W - 1) >= TARGET_SZ) {
				//cout << "x = " << x << " -> " << i << " " << j << endl;
				return true;
			}

		return false;
	});

	return res;
}

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