oj.uz

Submission #912807

# Submission time Handle Problem Language Result Execution time Memory
912807 2024-01-19T23:55:57 Z OAleksa Quality Of Living (IOI10_quality) C++14
100 / 100
 1862 ms 140540 KB 
#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 Q[3001][3001];
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 - 1, j + W - 1) >= (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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 15 ms 5464 KB Output is correct
8 Correct 15 ms 5472 KB Output is correct
9 Correct 13 ms 5316 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 15 ms 5464 KB Output is correct
8 Correct 15 ms 5472 KB Output is correct
9 Correct 13 ms 5316 KB Output is correct
10 Correct 176 ms 23380 KB Output is correct
11 Correct 174 ms 23376 KB Output is correct
12 Correct 88 ms 18004 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2492 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 15 ms 5464 KB Output is correct
8 Correct 15 ms 5472 KB Output is correct
9 Correct 13 ms 5316 KB Output is correct
10 Correct 176 ms 23380 KB Output is correct
11 Correct 174 ms 23376 KB Output is correct
12 Correct 88 ms 18004 KB Output is correct
13 Correct 1862 ms 140516 KB Output is correct
14 Correct 1831 ms 140540 KB Output is correct
15 Correct 1709 ms 130032 KB Output is correct