Submission #856808

#	Time	Username	Problem	Language	Result	Execution time	Memory
856808		drome	Quality Of Living (IOI10_quality)	C++14	100 / 100	3830 ms	175468 KiB

quality

#include "quality.h"
#include <string.h>
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	ll lo = 1, hi = R * C;

	int leq[3001][3001];
	int ps[3001][3001];


	for (int _=0;_<100;_++) {
		ll mi = (lo + hi) / 2;
		memset(leq, 0, sizeof(leq));
		for (int i=0;i<R;i++) for (int j=0;j<C;j++) {
			leq[i][j] = (Q[i][j] <= mi);
			ps[i][j] = leq[i][j];
			if (i) ps[i][j] += ps[i-1][j];
			if (j) ps[i][j] += ps[i][j-1];
			if (i && j) ps[i][j] -= ps[i-1][j-1];
		}

		// cout << "MI: " << mi << endl;
		// for (int i=0;i<R;i++) {
		// 	for (int j=0;j<C;j++) {
		// 		cout << leq[i][j] << " ";
		// 	}
		// 	cout << endl;
		// }

		// for (int i=0;i<R;i++) {
		// 	for (int j=0;j<C;j++) {
		// 		cout << ps[i][j] << " ";
		// 	}
		// 	cout << endl;
		// }

		ll maxsum = 0;
		for (int i=0;i+H<=R;i++) for (int j=0;j+W<=C;j++) {
			ll sum = ps[i+H-1][j+W-1];
			if (i) sum -= ps[i-1][j+W-1];
			if (j) sum -= ps[i+H-1][j-1];
			if (i && j) sum += ps[i-1][j-1];
			maxsum = max(maxsum, sum);
		}

		// cout << "maxsum: " << maxsum << endl;

		if (maxsum > (W * H) / 2) hi = mi;
		else lo = mi + 1;
	}


	return lo;
}

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