Submission #292239

#	Time	Username	Problem	Language	Result	Execution time	Memory
292239		amiratou	Quality Of Living (IOI10_quality)	C++14	100 / 100	2453 ms	103572 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
int cum[3001][3001];
int sum(int a,int b,int c,int d){
	int ans=cum[c][d];
	if(a)ans-=cum[a-1][d];
	if(b)ans-=cum[c][b-1];
	if(a && b)ans+=cum[a-1][b-1];
	return ans;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l=1,r=R*C,cons=(H*W)/2,ans=-1;
	while(l<=r){
		int med=(l+r)>>1;
		for (int i = 0; i < R; ++i)
			for (int j = 0; j < C; ++j)
			{
				cum[i][j]=(Q[i][j]<=med);
				if(i)cum[i][j]+=cum[i-1][j];
				if(j)cum[i][j]+=cum[i][j-1];
				if(i&&j)cum[i][j]-=cum[i-1][j-1];
			}
		bool f=0;
		for (int i = 0; i+H-1 < R; ++i)
		{
			for (int j = 0; j+W-1 < C; ++j)
				if(sum(i,j,i+H-1,j+W-1)>(cons)){
					f=1;break;
				}
			if(f)break;
		}
		if(f)r=med-1,ans=med;
		else l=med+1;
	}
	assert(ans!=-1);
	return ans;
}

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