답안 #958108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958108	2024-04-04T23:51:24 Z	pedroslrey	삶의 질 (IOI10_quality)	C++17	100 / 100	1735 ms	71436 KB

quality

#include <bits/stdc++.h>

using namespace std;

bool check(int n, int m, int h, int w, int ms[3001][3001], int mid) {
	vector<vector<int>> cnt(n + 1, vector<int>(m + 1));

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			int val = ms[i-1][j-1] <= mid;

			cnt[i][j] = cnt[i][j-1] + cnt[i-1][j] - cnt[i-1][j-1] + val;
		}

	for (int i = h; i <= n; ++i)
		for (int j = w; j <= m; ++j)
			if (cnt[i][j] - cnt[i - h][j] - cnt[i][j - w] + cnt[i - h][j - w] > h*w/2) return true;

	return false;
}

int rectangle(int n, int m, int h, int w, int ms[3001][3001]) {
	int l = 1, r = n*m;
	while (l < r) {
		int mid = (l + r)/2;

		if (check(n, m, h, w, ms, mid)) r = mid;
		else l = mid + 1;
	}

	return l;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2652 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2652 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	2 ms	2396 KB	Output is correct
6	Correct	2 ms	2396 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2652 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	2 ms	2396 KB	Output is correct
6	Correct	2 ms	2396 KB	Output is correct
7	Correct	13 ms	4984 KB	Output is correct
8	Correct	13 ms	4960 KB	Output is correct
9	Correct	12 ms	4968 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2652 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	2 ms	2396 KB	Output is correct
6	Correct	2 ms	2396 KB	Output is correct
7	Correct	13 ms	4984 KB	Output is correct
8	Correct	13 ms	4960 KB	Output is correct
9	Correct	12 ms	4968 KB	Output is correct
10	Correct	162 ms	16856 KB	Output is correct
11	Correct	167 ms	16876 KB	Output is correct
12	Correct	80 ms	14856 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2652 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	2 ms	2396 KB	Output is correct
6	Correct	2 ms	2396 KB	Output is correct
7	Correct	13 ms	4984 KB	Output is correct
8	Correct	13 ms	4960 KB	Output is correct
9	Correct	12 ms	4968 KB	Output is correct
10	Correct	162 ms	16856 KB	Output is correct
11	Correct	167 ms	16876 KB	Output is correct
12	Correct	80 ms	14856 KB	Output is correct
13	Correct	1735 ms	71436 KB	Output is correct
14	Correct	1657 ms	71200 KB	Output is correct
15	Correct	1508 ms	67540 KB	Output is correct