Submission #201507

#	Time	Username	Problem	Language	Result	Execution time	Memory
201507		luciocf	Quality Of Living (IOI10_quality)	C++14	100 / 100	3695 ms	142200 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"

using namespace std;

const int maxn = 3010;

int n, m, h, w;

int a[maxn][maxn];

int aux[maxn][maxn];
int soma[maxn][maxn];

bool ok(int x)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (a[i][j] > x) aux[i][j] = 1;
			else if (a[i][j] == x) aux[i][j] = 0;
			else aux[i][j] = -1;
		}
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			soma[i][j] = soma[i-1][j]+soma[i][j-1]+aux[i][j]-soma[i-1][j-1];

	for (int i = 1; i+h-1 <= n; i++)
		for (int j = 1; j+w-1 <= m; j++)
			if (soma[i+h-1][j+w-1]-soma[i+h-1][j-1]-soma[i-1][j+w-1]+soma[i-1][j-1] <= 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;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			a[i][j] = A[i-1][j-1];


	int ini = 1, fim = n*m, ans = n*m;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		if (ok(mid)) ans = mid, fim = mid-1;
		else ini = mid+1;
	}

	return ans;
}

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