Submission #404469

#	Time	Username	Problem	Language	Result	Execution time	Memory
404469		Drew_	Quality Of Living (IOI10_quality)	C++17	100 / 100	2624 ms	89936 KiB

quality

#include "quality.h"
#include <functional>
using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {

	int pfx[3001][3001];
	function<bool(int)> check = [&](int x)
	{
		for (int i = 1; i <= R; ++i)
		{
			for (int j = 1; j <= C; ++j)
			{
				if (Q[i-1][j-1] > x) pfx[i][j] = -1;
				else pfx[i][j] = 1; 

				pfx[i][j] += pfx[i-1][j] + pfx[i][j-1] - pfx[i-1][j-1];
			}
		}

		int mx = -1e9;
		for (int i = 1; i <= R-H+1; ++i)
		{
			for (int j = 1; j <= C-W+1; ++j)
			{
				//sum from (i, j) to (i+H-1, j+W-1)
				mx = max(mx, pfx[i+H-1][j+W-1] - pfx[i+H-1][j-1] - pfx[i-1][j+W-1] + pfx[i-1][j-1]);
			}
		}
		return mx >= 0;
	};

	int l = 1, r = R*C;
	while (l < r)
	{
		int mid = (l + r) >> 1;
		if (check(mid)) 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