Submission #887405

#	Time	Username	Problem	Language	Result	Execution time	Memory
887405		Faisal_Saqib	Quality Of Living (IOI10_quality)	C++17	100 / 100	1350 ms	180224 KiB

quality

#include <iostream>
using namespace std;
int n,m,h,w,g[3100][3100],pre[3100][3100];
bool check(int& k)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			pre[i][j]=((g[i][j]<=k)?1:-1)+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
	for(int i=1;(i+h-1)<=n;i++)
		for(int j=1;(j+w-1)<=m;j++)
			if((pre[i+h-1][j+w-1]-pre[i-1][j+w-1]-pre[i+h-1][j-1]+pre[i-1][j-1])>=0)
				return 1;
	return 0;
}
int rectangle(int n1, int m1, int h1, int w1, int g1[3001][3001])
{
	n=n1,m=m1,h=h1,w=w1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			g[i][j]=g1[i-1][j-1];
	int s=0,e=n*m;
	while(s+1<e)
	{
		int mid=(s+e)/2;
		if(check(mid))
			e=mid;
		else
			s=mid;
	}
	return e;
}

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