제출 #958101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958101		Hacv16	삶의 질 (IOI10_quality)	C++17	100 / 100	1857 ms	71464 KiB

quality

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

int rectangle(int n, int m, int h, int w, int q[3001][3001])
{
	auto f = [&](int x)
	{
		vector<vector<int>> sums(n + 10, vector<int>(m + 10));

		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + (q[i - 1][j - 1] <= x);

		for(int i = h; i <= n; i++)
		{
			for(int j = w; j <= m; j++)
			{
				int curSum = sums[i][j] - sums[i - h][j] - sums[i][j - w] + sums[i - h][j - w];
				if(2 * curSum >= h * w) return true;
			}
		}

		return false;
	};

	int l = 1, r = n * m;

	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(f(mid)) r = mid;
		else l = mid + 1;
	}

	return r;
}

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