Submission #1191815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191815		peteza	Quality Of Living (IOI10_quality)	C++20	100 / 100	1128 ms	70896 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;

int qs[3001][3001];

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 1, r = R*C, mid;
	int medcnt = H*W/2+1;
	while(l <= r) {
		mid = (l+r) >> 1;
		for(int i=0;i<R;i++) {
			for(int j=0;j<C;j++) {
				qs[i+1][j+1] = (Q[i][j] <= mid);
				qs[i+1][j+1] += qs[i+1][j] + qs[i][j+1] - qs[i][j];
			}
		}
		int cnt = 0;
		for(int i=0;i+H<=R;i++) {
			for(int j=0;j+W<=C;j++) {
				cnt = max(cnt, qs[i+H][j+W] - qs[i+H][j] - qs[i][j+W] + qs[i][j]);
			}
		}
		if(cnt >= medcnt) 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