Submission #976519

#	Time	Username	Problem	Language	Result	Execution time	Memory
976519		SoSmolSten	Quality Of Living (IOI10_quality)	C++17	0 / 100	1 ms	2396 KiB

quality

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

ll pref[3001][3001];
int getsum(int i, int j, int h, int w){
	return pref[i][j] - pref[i - h][j] - pref[i][j - w] + pref[i - h][j - w];
}

bool f(int med, int n, int m, int h, int w, int a[3001][3001]){
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j) {
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + (a[i - 1][j - 1] >= med);
		}
	}
	for(int i = h; i <= n; ++i){
		for(int j = w; j <= m; ++j) {
			if(getsum(i, j, h, w) >= (h * w + 1) / 2) return 1;
		}
	}
	return 0;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 0, r = R * C + 1;
	while(l + 1 < r){
		int mid = (l + r) / 2;
		if(f(mid, R, C, H, W, Q)) l = mid;
		else r = mid;
	}
	return l;
}

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