Submission #996438

#	Time	Username	Problem	Language	Result	Execution time	Memory
996438		yellowtoad	Quality Of Living (IOI10_quality)	C++17	100 / 100	2576 ms	175188 KiB

quality

#include "quality.h"
#include <iostream>
using namespace std;

int b[3001][3001], c[3001][3001], maxx, minn;

int rectangle(int n, int m, int h, int w, int a[3001][3001]) {
	int l = 1, r = n*m;
	while (l <= r) {
		int mid = (l+r)/2;
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[i][j] = c[i][j] = 0;
		for (int j = 0; j < m; j++) {
			for (int i = 0; i < h; i++) {
				if (a[i][j] > mid) b[0][j]++;
				else c[0][j]++;
			}
			for (int i = 0; i+h < n; i++) {
				b[i+1][j] = b[i][j];
				c[i+1][j] = c[i][j];
				if (a[i][j] > mid) b[i+1][j]--;
				else c[i+1][j]--;
				if (a[i+h][j] > mid) b[i+1][j]++;
				else c[i+1][j]++;
			}
		}
		/*for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << b[i][j] << " ";
			} cout << endl;
		}*/
		for (int i = 0; i+h-1 < n; i++) {
			maxx = minn = 0;
			for (int j = 0; j < w; j++) maxx += b[i][j], minn += c[i][j];
			if (minn > maxx) {
				r = mid-1;
				goto skip;
			}
			for (int j = w; j < m; j++) {
				maxx -= b[i][j-w];
				minn -= c[i][j-w];
				maxx += b[i][j];
				minn += c[i][j];
				if (minn > maxx) {
					r = mid-1;
					goto skip;
				}
			}
		}
		l = mid+1;
		skip:;
	}
	return l;
}

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