Submission #595931

#	Time	Username	Problem	Language	Result	Execution time	Memory
595931		BT21tata	Quality Of Living (IOI10_quality)	C++17	100 / 100	2045 ms	108372 KiB

quality

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

int cnt[3005][3005], q[3005][3005];

bool check(int num, int r, int c, int h, int w)
{
	//cout<<num<<endl;
	memset(cnt, 0, sizeof(cnt));
	for(int i=1; i<=r; i++)
		for(int j=1; j<=c; j++)
		{
			//cout<<cnt[i-1][j]<<' '<<cnt[i][j-1]<<' '<<cnt[i-1][j-1]<<' '<<q[i][j]<<' '<<(q[i][j]<num)<<endl;
			cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+(q[i][j]<=num)/*, cout<<i<<' '<<j<<' '<<cnt[i][j]<<endl*/;
		}
	
	for(int i=1; i<=r; i++)
	{
		for(int j=1; j<=c; j++)
		{
			if(i+h-1>r) continue;
			if(j+w-1>c) continue;
			int sum=cnt[i+h-1][j+w-1]-cnt[i-1][j+w-1]-cnt[i+h-1][j-1]+cnt[i-1][j-1];
			//cout<<"sum  "<<i<<' '<<j<<' '<<sum<<endl;
			if(sum>h*w/2) return 1;
		}
	}
	return 0;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
	int l=1, r=R*C, mid;
	for(int i=0; i<R; i++)
	{
		for(int j=0; j<C; j++)
		{
			q[i+1][j+1]=Q[i][j];
		}
	}
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid, R, C, H, W)) r=mid-1;
		else l=mid+1;
	}
	return l;
}

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