Submission #411895

#	Time	Username	Problem	Language	Result	Execution time	Memory
411895		Berted	Quality Of Living (IOI10_quality)	C++14	100 / 100	2224 ms	150444 KiB

quality

#include "quality.h"
#include <algorithm>

using namespace std;

int r, c, h, w, pref[3001][3001], A[3001][3001];

inline int query(int x1, int y1, int x2, int y2) {return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];}

inline bool solve(int x)
{
	for (int i = 1; i <= r; i++)
	{
		for (int j = 1; j <= c; j++)
		{
			pref[i][j] = A[i][j] <= x;
			pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
		}
	}
	int mx = 0;
	for (int i = h; i <= r; i++)
	{
		for (int j = w; j <= c; j++)
		{
			mx = max(mx, query(i - h + 1, j - w + 1, i, j));
		}
	}
	return mx > h * w / 2;
}

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 = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++) A[i][j] = Q[i - 1][j - 1];
	}

	int lf = 1, rg = R * C + 1;
	while (lf < rg)
	{
		int M = lf + rg >> 1;
		if (solve(M)) rg = M;
		else lf = M + 1;
	}

	return lf;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int M = lf + rg >> 1;
      |           ~~~^~~~

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