oj.uz

Submission #201479

# Submission time Handle Problem Language Result Execution time Memory
201479 2020-02-10T17:07:12 Z dolphingarlic Quality Of Living (IOI10_quality) C++14
100 / 100
 3074 ms 175732 KB 
#include "grader.h"

int lg[3001][3001], pref[3001][3001];

bool check(int median, int R, int C, int H, int W, int Q[3001][3001]) {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (Q[i][j] > median) lg[i + 1][j + 1] = 1;
			else if (Q[i][j] == median) lg[i + 1][j + 1] = 0;
			else lg[i + 1][j + 1] = -1;

			pref[i + 1][j + 1] = lg[i + 1][j + 1] + pref[i + 1][j] + pref[i][j + 1] - pref[i][j];
		}
	}

	for (int i = H; i <= R; i++) {
		for (int j = W; j <= C; j++) {
			if (pref[i][j] + pref[i - H][j - W] - pref[i][j - W] - pref[i - H][j] <= 0) return true;
		}
	}
	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 1, r = R * C;
	while (l != r) {
		int mid = (l + r) / 2;
		if (check(mid, R, C, H, W, Q)) r = mid;
		else l = mid + 1;
	}
	return l;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 636 KB Output is correct
3 Correct 5 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 636 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 7 ms 1660 KB Output is correct
5 Correct 7 ms 1656 KB Output is correct
6 Correct 8 ms 1656 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 636 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 7 ms 1660 KB Output is correct
5 Correct 7 ms 1656 KB Output is correct
6 Correct 8 ms 1656 KB Output is correct
7 Correct 30 ms 5496 KB Output is correct
8 Correct 31 ms 5496 KB Output is correct
9 Correct 32 ms 5368 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 636 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 7 ms 1660 KB Output is correct
5 Correct 7 ms 1656 KB Output is correct
6 Correct 8 ms 1656 KB Output is correct
7 Correct 30 ms 5496 KB Output is correct
8 Correct 31 ms 5496 KB Output is correct
9 Correct 32 ms 5368 KB Output is correct
10 Correct 332 ms 30968 KB Output is correct
11 Correct 324 ms 30840 KB Output is correct
12 Correct 169 ms 21608 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 5 ms 636 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 7 ms 1660 KB Output is correct
5 Correct 7 ms 1656 KB Output is correct
6 Correct 8 ms 1656 KB Output is correct
7 Correct 30 ms 5496 KB Output is correct
8 Correct 31 ms 5496 KB Output is correct
9 Correct 32 ms 5368 KB Output is correct
10 Correct 332 ms 30968 KB Output is correct
11 Correct 324 ms 30840 KB Output is correct
12 Correct 169 ms 21608 KB Output is correct
13 Correct 3074 ms 175732 KB Output is correct
14 Correct 3024 ms 175476 KB Output is correct
15 Correct 2779 ms 168420 KB Output is correct