Submission #1035211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035211		abczz	Quality Of Living (IOI10_quality)	C++17	100 / 100	1098 ms	175188 KiB

quality

#include "quality.h"
#include <iostream>
#define ll long long

using namespace std;

bool ok;
ll ps[3000][3000], l, r, mid, cur;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	l = 1, r = R*C;
	while (l < r) {
		ok = 0;
		mid = (l+r)/2;
		for (int i=0; i<R; ++i) {
			for (int j=0; j<C; ++j) {
				ps[i][j] = (Q[i][j] <= mid ? 1 : 0);
				if (i && j) ps[i][j] += ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1];
				else if (i) ps[i][j] += ps[i-1][j];
				else if (j) ps[i][j] += ps[i][j-1];
				if (i >= H-1 && j >= W-1) {
					cur = ps[i][j];
					if (i != H-1 && j != W-1) cur -= ps[i-H][j] + ps[i][j-W] - ps[i-H][j-W];
					else if (i != H-1) cur -= ps[i-H][j];
					else if (j != W-1) cur -= ps[i][j-W];
					if (cur >= (H*W+1)/2) ok = 1;
				}
			}
		}
		if (ok) r = mid;
		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