Submission #1013315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013315		ThommyDB	Quality Of Living (IOI10_quality)	C++17	100 / 100	1544 ms	140076 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>

using namespace std;

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)/2;
		for(int i = 0; i < R; i++){
			for(int j = 0; j < C; j++){
				if(Q[i][j] <= mid) a[i+1][j+1]=1;
				else a[i+1][j+1]=-1;
				a[i+1][j+1] += a[i+1][j]+a[i][j+1]-a[i][j];
			}
		}

		bool yes= false;
		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]> -1){
					yes=true;
					break;
				}
			}
			if(yes)break;
		}
		if(yes){
			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