Submission #837899

#	Time	Username	Problem	Language	Result	Execution time	Memory
837899		thimote75	Quality Of Living (IOI10_quality)	C++14	100 / 100	1497 ms	175488 KiB

quality

#include "quality.h"

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

using idata = vector<int>;
using igrid = vector<idata>;

igrid VC;

bool check (int R, int C, int H, int W, igrid &V, int M) {
	int count = (H * W + 1) >> 1;

	for (int i = 0; i <= R; i ++)
		VC[i][0] = 0;
	for (int i = 0; i <= C; i ++)
		VC[0][i] = 0;

	for (int i = 1; i <= R; i ++) {
		for (int j = 1; j <= C; j ++) {
			VC[i][j] = VC[i - 1][j]
			         + VC[i][j - 1]
					 - VC[i - 1][j - 1]
					 + (V[i - 1][j - 1] <= M ? 1 : 0);
		}
	}

	for (int i = 0; i + H <= R; i ++) {
		for (int j = 0; j + W <= C; j ++) {
			int lc = VC[i][j] + VC[i + H][j + W]
			      - (VC[i + H][j] + VC[i][j + W]);
			
			if (lc >= count) return true;
		}
	}

	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	VC.resize(R + 1, idata(C + 1));
	igrid V(R, idata(C));
	for (int i = 0; i < R; i ++)
		for (int j = 0; j < C; j ++)
			V[i][j] = Q[i][j];
	
	int a = 0;
	int b = R * C;

	while (b - a > 1) {
		int c = (a + b) >> 1;

		if (check(R, C, H, W, V, c)) b = c;
		else a = c;
	}

	return b;
}

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