답안 #240141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240141	2020-06-18T07:30:43 Z	staniewzki	삶의 질 (IOI10_quality)	C++17	100 / 100	2332 ms	71256 KB

quality

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#include "quality.h"

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	auto check = [&](int m) {
		vector<vector<int>> pref(R + 1, vector<int>(C + 1));
		FOR(i, 0, R - 1) FOR(j, 0, C - 1) {
			int v = (Q[i][j] <= m ? +1 : -1);
			pref[i + 1][j + 1] = pref[i + 1][j] + pref[i][j + 1] - pref[i][j] + v;
		}

		FOR(i, H, R) FOR(j, W, C) {
			if(pref[i][j] - pref[i - H][j] - pref[i][j - W] + pref[i - H][j - W] >= 1)
				return true;
		}
		return false;
	};

	int l = 1, r = R * C;
	while(l < r) {
		int m = (l + r) / 2;
		if(check(m))
			r = m;
		else
			l = m + 1;
	}
	return l;
}

Subtask #1

20.0 / 20.0

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

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	6 ms	768 KB	Output is correct
5	Correct	7 ms	768 KB	Output is correct
6	Correct	6 ms	768 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	6 ms	768 KB	Output is correct
5	Correct	7 ms	768 KB	Output is correct
6	Correct	6 ms	768 KB	Output is correct
7	Correct	28 ms	2316 KB	Output is correct
8	Correct	31 ms	2276 KB	Output is correct
9	Correct	21 ms	2212 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	6 ms	768 KB	Output is correct
5	Correct	7 ms	768 KB	Output is correct
6	Correct	6 ms	768 KB	Output is correct
7	Correct	28 ms	2316 KB	Output is correct
8	Correct	31 ms	2276 KB	Output is correct
9	Correct	21 ms	2212 KB	Output is correct
10	Correct	266 ms	12288 KB	Output is correct
11	Correct	248 ms	12368 KB	Output is correct
12	Correct	120 ms	8376 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	6 ms	768 KB	Output is correct
5	Correct	7 ms	768 KB	Output is correct
6	Correct	6 ms	768 KB	Output is correct
7	Correct	28 ms	2316 KB	Output is correct
8	Correct	31 ms	2276 KB	Output is correct
9	Correct	21 ms	2212 KB	Output is correct
10	Correct	266 ms	12288 KB	Output is correct
11	Correct	248 ms	12368 KB	Output is correct
12	Correct	120 ms	8376 KB	Output is correct
13	Correct	2332 ms	71108 KB	Output is correct
14	Correct	2322 ms	71256 KB	Output is correct
15	Correct	2125 ms	67756 KB	Output is correct