답안 #512673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
512673	2022-01-16T16:18:14 Z	saral	삶의 질 (IOI10_quality)	C++14	100 / 100	1855 ms	106256 KB

quality

#include "quality.h"
const int N = 3010;
int pom[N][N], b[N][N];

bool check (int x, int n, int m, int h, int w, int a[N][N]) {
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			pom[i][j] = 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] <= x) pom[i][j] = 1;
			else pom[i][j] = 0;
			pom[i][j] = pom[i][j]+pom[i-1][j]+pom[i][j-1]-pom[i-1][j-1];
		}
	}
	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << pom[i][j] << " ";
		}
		cout << endl;
	}*/
	for (int i = h; i <= n; i++) {
		for (int j = w; j <= m; j++) {
			int val = pom[i][j]-pom[i-h][j]-pom[i][j-w]+pom[i-h][j-w];
			if (val >= (h*w+1)/2) return true;
		}
	}
	return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int lo = 1, hi = R*C, mid;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			b[i+1][j+1] = Q[i][j];
		}
	}
	while (lo < hi) {
		mid = (lo+hi)/2;
		if (check(mid, R, C, H, W, b)) {
			hi = mid;
		}
		else {
			lo = mid+1;
		}
	}
	return lo;
}

Subtask #1

20.0 / 20.0

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

Subtask #2

20.0 / 20.0

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

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	588 KB	Output is correct
3	Correct	0 ms	588 KB	Output is correct
4	Correct	2 ms	1612 KB	Output is correct
5	Correct	2 ms	1612 KB	Output is correct
6	Correct	2 ms	1612 KB	Output is correct
7	Correct	16 ms	4940 KB	Output is correct
8	Correct	16 ms	4992 KB	Output is correct
9	Correct	14 ms	4840 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	588 KB	Output is correct
3	Correct	0 ms	588 KB	Output is correct
4	Correct	2 ms	1612 KB	Output is correct
5	Correct	2 ms	1612 KB	Output is correct
6	Correct	2 ms	1612 KB	Output is correct
7	Correct	16 ms	4940 KB	Output is correct
8	Correct	16 ms	4992 KB	Output is correct
9	Correct	14 ms	4840 KB	Output is correct
10	Correct	220 ms	24108 KB	Output is correct
11	Correct	181 ms	24068 KB	Output is correct
12	Correct	97 ms	18208 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	588 KB	Output is correct
3	Correct	0 ms	588 KB	Output is correct
4	Correct	2 ms	1612 KB	Output is correct
5	Correct	2 ms	1612 KB	Output is correct
6	Correct	2 ms	1612 KB	Output is correct
7	Correct	16 ms	4940 KB	Output is correct
8	Correct	16 ms	4992 KB	Output is correct
9	Correct	14 ms	4840 KB	Output is correct
10	Correct	220 ms	24108 KB	Output is correct
11	Correct	181 ms	24068 KB	Output is correct
12	Correct	97 ms	18208 KB	Output is correct
13	Correct	1840 ms	106212 KB	Output is correct
14	Correct	1855 ms	106256 KB	Output is correct
15	Correct	1705 ms	106148 KB	Output is correct