Submission #912806

#	Time	Username	Problem	Language	Result	Execution time	Memory
912806		OAleksa	Quality Of Living (IOI10_quality)	C++14	0 / 100	1 ms	2396 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
//#define int long long
#define f first
#define s second
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int n = R, m = C;
	int l = 1, r = n * m, ans = R * C;
	vector<vector<int>> p(n, vector<int>(m));
	auto Get = [&](int x1, int y1, int x2, int y2) {
		int res = 0;
		res += p[x2][y2];
		if (x2 >= H)
			res -= p[x2 - H][y2];
		if (y2 >= W)
			res -= p[x2][y2 - W];
		if (x2 >= H && y2 >= W)
			res += p[x2 - H][y2 - W];
		return res;
	};
	auto check = [&](int mid) {
		for (int i = 0;i < n;i++)
			for (int j = 0;j < m;j++)
				p[i][j] = 0;
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < m;j++) {
				if (Q[i][j] <= mid)
					p[i][j]++;
				if (i > 0 && j > 0) 
					p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
				else if (i > 0)
					p[i][j] += p[i - 1][j];
				else if (j > 0)
					p[i][j] += p[i][j - 1];
			}
		}
		int sz = H * W;
		assert(sz % 2 == 1);
		for (int i = 0;i + H < n;i++) {
			for (int j = 0;j + W < m;j++) {
				if (Get(i, j, i + H, j + W) >= (sz + 1) / 2)
					return true;
			}
		}
		return false;
	};
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	return ans;
}

// signed main() {
  // ios::sync_with_stdio(false);
  // cin.tie(0);
  // cout.tie(0);
  // int tt = 1;
  // //cin >> tt;
  // while (tt--) {
  	// int r, c, h, w;
  	// cin >> r >> c >> h >> w;
  	// for (int i = 0;i < r;i++)
  		// for (int j = 0;j < c;j++)
  			// cin >> Q[i][j];
  	// cout << rectangle(r, c, h, w, Q) << '\n';
	// }
  // return 0;
// }

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