Submission #298471

#	Time	Username	Problem	Language	Result	Execution time	Memory
298471		Hemimor	Quality Of Living (IOI10_quality)	C++14	100 / 100	1931 ms	93816 KiB

quality

#include "quality.h"
#include <iostream>
using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l=0,r=R*C;
	auto f=[&](int x){
		int a[3001][3001];
		for(int i=0;i<=R;i++) for(int j=0;j<=C;j++) a[i][j]=0;
		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=0;i<=R;i++){
			for(int j=0;j<=C;j++) cout<<a[i][j]<<' ';
			cout<<endl;
		}
		cout<<endl;
		cout<<x<<' '<<H<<' '<<R<<' '<<W<<' '<<C<<endl;*/
		for(int i=H;i<=R;i++) for(int j=W;j<=C;j++){
//			cout<<i<<' '<<j<<' '<<a[i][j]-a[i-H][j]-a[i][j-W]+a[i-H][j-W]<<endl;
			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)) r=m;
		else l=m;
	}
	return r;
}

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