Submission #684445

#	Time	Username	Problem	Language	Result	Execution time	Memory
684445		onlk97	Quality Of Living (IOI10_quality)	C++14	100 / 100	1670 ms	140148 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
	int l=1,r=R*C;
	int ps[R+1][C+1];
	while (l<r){
		int mid=(l+r)/2;
		for (int i=0; i<=R; i++){
			for (int j=0; j<=C; j++) ps[i][j]=0;
		}
		for (int i=1; i<=R; i++){
			for (int j=1; j<=C; j++){
				ps[i][j]=ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1]+(Q[i-1][j-1]<=mid);
			}
		}
		bool ok=0;
		for (int i=H; i<=R; i++){
			for (int j=W; j<=C; j++){
				if (ps[i][j]-ps[i-H][j]-ps[i][j-W]+ps[i-H][j-W]>=(H*W+1)/2) ok=1;
			}
		}
		if (ok) r=mid;
		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