Submission #298469

#	Time	Username	Problem	Language	Result	Execution time	Memory
298469		Hemimor	Quality Of Living (IOI10_quality)	C++14	0 / 100	1 ms	512 KiB

quality

#include "quality.h"

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l=1,r=R*C+1;
	auto f=[&](int x){
		int a[3001][3001];
		for(int i=0;i<R;i++) for(int j=0;j<C;j++){
			a[i+1][j+1]=a[i][j+1]+a[i+1][j]-a[i][j]+(Q[i][j]<=x?1:0);
		}
		for(int i=H;i<R;i++) for(int j=W;j<C;j++) if(a[i][j]-a[i-H][j]-a[i][j-W]+a[i-H][j-W]>H*W/2) return 1;
		return 0;
	};
	while(r-l>1){
		int m=(l+r)/2;
		if(f(m)) l=m;
		else r=m;
	}
	return l;
}

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