답안 #240139

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

quality

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for(int i = 0; i < n; i++)
#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));
		REP(i, R) REP(j, C) {
			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	512 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	404 KB	Output is correct

Subtask #2

20.0 / 20.0

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

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	512 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	404 KB	Output is correct
4	Correct	7 ms	896 KB	Output is correct
5	Correct	6 ms	896 KB	Output is correct
6	Correct	6 ms	896 KB	Output is correct
7	Correct	28 ms	2996 KB	Output is correct
8	Correct	23 ms	2856 KB	Output is correct
9	Correct	32 ms	2692 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	512 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	404 KB	Output is correct
4	Correct	7 ms	896 KB	Output is correct
5	Correct	6 ms	896 KB	Output is correct
6	Correct	6 ms	896 KB	Output is correct
7	Correct	28 ms	2996 KB	Output is correct
8	Correct	23 ms	2856 KB	Output is correct
9	Correct	32 ms	2692 KB	Output is correct
10	Correct	249 ms	19016 KB	Output is correct
11	Correct	261 ms	19040 KB	Output is correct
12	Correct	121 ms	11760 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	512 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	404 KB	Output is correct
4	Correct	7 ms	896 KB	Output is correct
5	Correct	6 ms	896 KB	Output is correct
6	Correct	6 ms	896 KB	Output is correct
7	Correct	28 ms	2996 KB	Output is correct
8	Correct	23 ms	2856 KB	Output is correct
9	Correct	32 ms	2692 KB	Output is correct
10	Correct	249 ms	19016 KB	Output is correct
11	Correct	261 ms	19040 KB	Output is correct
12	Correct	121 ms	11760 KB	Output is correct
13	Correct	2491 ms	140504 KB	Output is correct
14	Correct	2387 ms	140544 KB	Output is correct
15	Correct	2268 ms	129856 KB	Output is correct