Submission #445592

#	Time	Username	Problem	Language	Result	Execution time	Memory
445592		prvocislo	Quality Of Living (IOI10_quality)	C++17	100 / 100	2009 ms	175652 KiB

quality

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

const int maxn = 3005;
int r, c, h, w;
vector<vector<int> > v(maxn, vector<int>(maxn));
bool check(int d) // cisla mensie ako d budu -1 a cisla vacsie ako d budu 1
{
	vector<vector<int>> pf(r+1, vector<int>(c+1, 0));
	for (int i = 0; i < r; i++) for (int j = 0; j < c; j++)
		pf[i+1][j+1] = (v[i][j] > d ? -1 : 1) + pf[i+1][j] + pf[i][j+1] - pf[i][j];
	for (int i = h; i <= r; i++) 
	{
		for (int j = w; j <= c; j++)
		{
			int sum = pf[i][j] - pf[i-h][j] - pf[i][j-w] + pf[i-h][j-w];
			if (sum > 0) return true;
		}
	}
	return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	r = R, c = C, h = H, w = W;
	for (int i = 0; i < r; i++) for (int j = 0; j < c; j++)
		v[i][j] = Q[i][j];
	int lo = 1, hi = (r * c);
	while (lo < hi)
	{
		int mi = (lo + hi) / 2;
		if (check(mi)) hi = mi;
		else lo = mi+1;
	}
	return lo;
}

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