Submission #366592

#	Time	Username	Problem	Language	Result	Execution time	Memory
366592		kostia244	Quality Of Living (IOI10_quality)	C++17	100 / 100	2664 ms	140560 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
int Q[3001][3001];
int rectangle(int R, int C, int H, int W, int tmp[3001][3001]) {
	auto can = [&](int x) {
		for(int it = 0; it < 3; it++)
		for(int i = 0; i < R; i++)
			for(int j = 0; j < C; j++) {
				if(it == 0) Q[i][j] = tmp[i][j] >= x ? -1 : 1;
				if(it == 1 && i) Q[i][j] += Q[i-1][j];
				if(it == 2 && j) Q[i][j] += Q[i][j-1];
			}
		for(int i = H-1; i < R; i++)
			for(int j = W-1; j < C; j++) {
				int res = Q[i][j];
				if(i-H>=0) res -= Q[i-H][j];
				if(j-W>=0) res -= Q[i][j-W];
				if(i-H>=0&&j-W>=0) res += Q[i-H][j-W];
				//cout << i << " " << j << " " << res << endl;
				if(res > 0) return 1;
			}
		return 0;
	};
	int ans = -1;
	for(int i = 1<<30; i>>=1;)
		ans += i*!can(ans+i);
	return ans;
}

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