답안 #408761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408761	2021-05-19T15:26:24 Z	rainboy	삶의 질 (IOI10_quality)	C	100 / 100	3687 ms	101680 KB

quality

#include "quality.h"

#define N	3000
#define M	3000

int solve(int aa[][3001], int n, int m, int k, int l, int a) {
	static int aa_[N + 1][M + 1];
	int i, j;

	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			aa_[i][j] = aa[i][j] <= a ? 1 : -1;
	for (i = 0; i < n; i++)
		for (j = m - 1; j >= 0; j--)
			aa_[i][j] += aa_[i][j + 1];
	for (j = 0; j < m; j++)
		for (i = n - 1; i >= 0; i--)
			aa_[i][j] += aa_[i + 1][j];
	for (i = 0; i + k <= n; i++)
		for (j = 0; j + l <= m; j++)
			if (aa_[i][j] - aa_[i][j + l] - aa_[i + k][j] + aa_[i + k][j + l] > 0)
				return 1;
	return 0;
}

int rectangle(int n, int m, int k, int l, int aa[][3001]) {
	int lower = 0, upper = n * m;

	while (upper - lower > 1) {
		int a = (lower + upper) / 2;

		if (solve(aa, n, m, k, l, a))
			upper = a;
		else
			lower = a;
	}
	return upper;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	536 KB	Output is correct
3	Correct	1 ms	540 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	536 KB	Output is correct
3	Correct	1 ms	540 KB	Output is correct
4	Correct	3 ms	1100 KB	Output is correct
5	Correct	3 ms	1100 KB	Output is correct
6	Correct	3 ms	1192 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	536 KB	Output is correct
3	Correct	1 ms	540 KB	Output is correct
4	Correct	3 ms	1100 KB	Output is correct
5	Correct	3 ms	1100 KB	Output is correct
6	Correct	3 ms	1192 KB	Output is correct
7	Correct	23 ms	3924 KB	Output is correct
8	Correct	23 ms	3916 KB	Output is correct
9	Correct	20 ms	3788 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	536 KB	Output is correct
3	Correct	1 ms	540 KB	Output is correct
4	Correct	3 ms	1100 KB	Output is correct
5	Correct	3 ms	1100 KB	Output is correct
6	Correct	3 ms	1192 KB	Output is correct
7	Correct	23 ms	3924 KB	Output is correct
8	Correct	23 ms	3916 KB	Output is correct
9	Correct	20 ms	3788 KB	Output is correct
10	Correct	284 ms	22816 KB	Output is correct
11	Correct	276 ms	22904 KB	Output is correct
12	Correct	141 ms	15500 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	536 KB	Output is correct
3	Correct	1 ms	540 KB	Output is correct
4	Correct	3 ms	1100 KB	Output is correct
5	Correct	3 ms	1100 KB	Output is correct
6	Correct	3 ms	1192 KB	Output is correct
7	Correct	23 ms	3924 KB	Output is correct
8	Correct	23 ms	3916 KB	Output is correct
9	Correct	20 ms	3788 KB	Output is correct
10	Correct	284 ms	22816 KB	Output is correct
11	Correct	276 ms	22904 KB	Output is correct
12	Correct	141 ms	15500 KB	Output is correct
13	Correct	3679 ms	101680 KB	Output is correct
14	Correct	3562 ms	101668 KB	Output is correct
15	Correct	3687 ms	98136 KB	Output is correct