oj.uz

Submission #958108

# Submission time Handle Problem Language Result Execution time Memory
958108 2024-04-04T23:51:24 Z pedroslrey Quality Of Living (IOI10_quality) C++17
100 / 100
 1735 ms 71436 KB 
#include <bits/stdc++.h>

using namespace std;

bool check(int n, int m, int h, int w, int ms[3001][3001], int mid) {
	vector<vector<int>> cnt(n + 1, vector<int>(m + 1));

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			int val = ms[i-1][j-1] <= mid;

			cnt[i][j] = cnt[i][j-1] + cnt[i-1][j] - cnt[i-1][j-1] + val;
		}

	for (int i = h; i <= n; ++i)
		for (int j = w; j <= m; ++j)
			if (cnt[i][j] - cnt[i - h][j] - cnt[i][j - w] + cnt[i - h][j - w] > h*w/2) return true;

	return false;
}

int rectangle(int n, int m, int h, int w, int ms[3001][3001]) {
	int l = 1, r = n*m;
	while (l < r) {
		int mid = (l + r)/2;

		if (check(n, m, h, w, ms, mid)) r = mid;
		else l = mid + 1;
	}

	return l;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 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 2652 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 13 ms 4984 KB Output is correct
8 Correct 13 ms 4960 KB Output is correct
9 Correct 12 ms 4968 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 13 ms 4984 KB Output is correct
8 Correct 13 ms 4960 KB Output is correct
9 Correct 12 ms 4968 KB Output is correct
10 Correct 162 ms 16856 KB Output is correct
11 Correct 167 ms 16876 KB Output is correct
12 Correct 80 ms 14856 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 13 ms 4984 KB Output is correct
8 Correct 13 ms 4960 KB Output is correct
9 Correct 12 ms 4968 KB Output is correct
10 Correct 162 ms 16856 KB Output is correct
11 Correct 167 ms 16876 KB Output is correct
12 Correct 80 ms 14856 KB Output is correct
13 Correct 1735 ms 71436 KB Output is correct
14 Correct 1657 ms 71200 KB Output is correct
15 Correct 1508 ms 67540 KB Output is correct