Submission #1012339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012339		huutuan	Quality Of Living (IOI10_quality)	C++14	100 / 100	1351 ms	140236 KiB

quality

#include "quality.h"

int a[3001][3001];

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l=1, r=R*C;
	while (l<=r){
		int mid=(l+r)>>1;
		for (int i=1; i<=R; ++i) for (int j=1; j<=C; ++j){
			a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1]+(Q[i-1][j-1]<=mid?1:-1);
		}
		bool check=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]>=0){
			check=1;
		}
		if (check) 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