oj.uz

Submission #958101

# Submission time Handle Problem Language Result Execution time Memory
958101 2024-04-04T22:56:14 Z Hacv16 Quality Of Living (IOI10_quality) C++17
100 / 100
 1857 ms 71464 KB 
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;

int rectangle(int n, int m, int h, int w, int q[3001][3001])
{
	auto f = [&](int x)
	{
		vector<vector<int>> sums(n + 10, vector<int>(m + 10));

		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + (q[i - 1][j - 1] <= x);

		for(int i = h; i <= n; i++)
		{
			for(int j = w; j <= m; j++)
			{
				int curSum = sums[i][j] - sums[i - h][j] - sums[i][j - w] + sums[i - h][j - w];
				if(2 * curSum >= h * w) return true;
			}
		}

		return false;
	};

	int l = 1, r = n * m;

	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(f(mid)) r = mid;
		else l = mid + 1;
	}

	return r;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 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 2 ms 2396 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 3 ms 2552 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 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 3 ms 2552 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 16 ms 4952 KB Output is correct
8 Correct 14 ms 4956 KB Output is correct
9 Correct 14 ms 4952 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 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 3 ms 2552 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 16 ms 4952 KB Output is correct
8 Correct 14 ms 4956 KB Output is correct
9 Correct 14 ms 4952 KB Output is correct
10 Correct 179 ms 16924 KB Output is correct
11 Correct 174 ms 16944 KB Output is correct
12 Correct 90 ms 14912 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 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 3 ms 2552 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 16 ms 4952 KB Output is correct
8 Correct 14 ms 4956 KB Output is correct
9 Correct 14 ms 4952 KB Output is correct
10 Correct 179 ms 16924 KB Output is correct
11 Correct 174 ms 16944 KB Output is correct
12 Correct 90 ms 14912 KB Output is correct
13 Correct 1845 ms 71464 KB Output is correct
14 Correct 1857 ms 71276 KB Output is correct
15 Correct 1652 ms 67976 KB Output is correct