Submission #1034543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034543		belgianbot	Quality Of Living (IOI10_quality)	C++14	0 / 100	1 ms	344 KiB

quality

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

using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = H *  W / 2 + 1, r = R * C - 1 - (H * W / 2);
	int ans = 1;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		bool possible = false;
		vector<vector<int>> nbSmaller (R, vector<int>(C - W + 1));
		vector<vector<int>> nbBigger (R, vector<int>(C - W + 1));
		for (int i = 0; i < R; i++) {
			int cnt = 0, cnt2 = 0;
			for (int j = 0; j < W; j++) {cnt += (Q[i][j] < mid); cnt2 += (Q[i][j] > mid);}
			nbSmaller[i][0] = cnt;
			nbBigger[i][0] = cnt2;
			for (int j = 0; j < C - W; j++) {
				cnt -= (Q[i][j] < mid);
				cnt += (Q[i][j + W] < mid);
				cnt2 -= (Q[i][j] > mid);
				cnt2 += (Q[i][j + W] > mid);
				nbSmaller[i][j + 1] = cnt;
				nbBigger[i][j + 1] = cnt2;
			}
		}
		/*cout << mid << '\n';
		for (auto x : nbSmaller) {
			for (auto y : x) cout << y << ' ';
			cout << '\n';
		}
		cout << "\n\n";*/
		for (int i = 0; i < C - W + 1; i++) {
			int cnt = 0, cnt2 = 0;
			for (int j = 0; j < H; j++) {cnt += nbSmaller[j][i]; cnt2 += nbBigger[j][i];}
			if (cnt == (W * H) / 2 && cnt + cnt2 < W * H) {
				possible = true;
				break;
			}
			for (int j = 0; j < R - H; j++) {
				cnt -= nbSmaller[j][i];
				cnt += nbSmaller[j + H][i];
				cnt2 -= nbBigger[j][i];
				cnt2 += nbBigger[j + H][i];
				if (cnt == (W * H) / 2 && cnt2 + cnt < W * H) {
					possible = true;
					break;
				}
			}
			if (possible) break;
		}
		if (possible) {
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	return ans;
}

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