oj.uz

Submission #532414

# Submission time Handle Problem Language Result Execution time Memory
532414 2022-03-02T21:23:37 Z sliviu Quality Of Living (IOI10_quality) C++17
100 / 100
 2237 ms 118584 KB 
#include <bits/stdc++.h>

using namespace std;

int rectangle(int N, int M, int y, int x, int q[3001][3001]) {
	int left = 1, right = N * M;
	while (left < right) {
		int m = (left + right) / 2;
		auto ok = [&](int cost) {
			vector<vector<int>> s(N + 1, vector<int>(M + 1));
			for (int i = 1; i <= N; ++i)
				for (int j = 1; j <= M; ++j)
					s[i][j] = ((q[i - 1][j - 1] < cost) ? -1 : (q[i - 1][j - 1] == cost ? 0 : 1)) + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
			for (int i = 1; i <= N - y + 1; ++i)
				for (int j = 1; j <= M - x + 1; ++j) {
					int ii = i + y - 1, jj = j + x - 1;
					if (s[ii][jj] - s[i - 1][jj] - s[ii][j - 1] + s[i - 1][j - 1] <= 0)
						return 1;
				}
			return 0;
		};
		if (ok(m))
			right = m;
		else
			left = m + 1;
	}
	return left;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 824 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 824 KB Output is correct
7 Correct 17 ms 2736 KB Output is correct
8 Correct 17 ms 2728 KB Output is correct
9 Correct 15 ms 2608 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 824 KB Output is correct
7 Correct 17 ms 2736 KB Output is correct
8 Correct 17 ms 2728 KB Output is correct
9 Correct 15 ms 2608 KB Output is correct
10 Correct 229 ms 19000 KB Output is correct
11 Correct 219 ms 18972 KB Output is correct
12 Correct 105 ms 11564 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 824 KB Output is correct
7 Correct 17 ms 2736 KB Output is correct
8 Correct 17 ms 2728 KB Output is correct
9 Correct 15 ms 2608 KB Output is correct
10 Correct 229 ms 19000 KB Output is correct
11 Correct 219 ms 18972 KB Output is correct
12 Correct 105 ms 11564 KB Output is correct
13 Correct 2237 ms 118496 KB Output is correct
14 Correct 2199 ms 118584 KB Output is correct
15 Correct 2001 ms 110452 KB Output is correct