oj.uz

Submission #943480

# Submission time Handle Problem Language Result Execution time Memory
943480 2024-03-11T14:13:15 Z IBory Quality Of Living (IOI10_quality) C++17
100 / 100
 3191 ms 177948 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = 3001;
int S[MAX][MAX], Y[MAX * MAX], X[MAX * MAX];

int rectangle(int R, int C, int H, int W, int S[MAX][MAX]) {
	for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) {
		int n = S[i][j];
		Y[n] = i, X[n] = j;
	}

	int l = 0, r = R * C + 1;
	while (l + 1 < r) {
		int mid = (l + r) >> 1;
		for (int i = 1; i <= mid; ++i) S[Y[i]][X[i]] = 1;
		for (int i = mid + 1; i <= R * C; ++i) S[Y[i]][X[i]] = 0;
		for (int i = 0; i < R; ++i) for (int j = 1; j < C; ++j) S[i][j] += S[i][j - 1];
		for (int j = 0; j < C; ++j) for (int i = 1; i < R; ++i) S[i][j] += S[i - 1][j];

		int high = 0;
		for (int i = H - 1; i < R; ++i) for (int j = W - 1; j < C; ++j) {
			int s = S[i][j] - (i >= H ? S[i - H][j] : 0) - (j >= W ? S[i][j - W] : 0) + (i >= H && j >= W ? S[i - H][j - W] : 0);
			high = max(high, s);
		}

		((H * W + 1) / 2 <= high ? r : l) = mid;
	}

	return r;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4540 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4540 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 16 ms 11356 KB Output is correct
8 Correct 16 ms 11188 KB Output is correct
9 Correct 14 ms 11340 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4540 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 16 ms 11356 KB Output is correct
8 Correct 16 ms 11188 KB Output is correct
9 Correct 14 ms 11340 KB Output is correct
10 Correct 201 ms 29720 KB Output is correct
11 Correct 196 ms 29912 KB Output is correct
12 Correct 98 ms 24428 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4540 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 16 ms 11356 KB Output is correct
8 Correct 16 ms 11188 KB Output is correct
9 Correct 14 ms 11340 KB Output is correct
10 Correct 201 ms 29720 KB Output is correct
11 Correct 196 ms 29912 KB Output is correct
12 Correct 98 ms 24428 KB Output is correct
13 Correct 3191 ms 177948 KB Output is correct
14 Correct 3177 ms 177948 KB Output is correct
15 Correct 2836 ms 164712 KB Output is correct