답안 #805275

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
805275	2023-08-03T14:43:13 Z	QwertyPi	삶의 질 (IOI10_quality)	C++14	100 / 100	1054 ms	140164 KB

quality

#include <bits/stdc++.h>

using namespace std;
int ps[3001][3001];
int sum(int x1, int x2, int y1, int y2){
	return ps[x2 + 1][y2 + 1] - ps[x2 + 1][y1] - ps[x1][y2 + 1] + ps[x1][y1];
}
 
bool ok(int R, int C, int H, int W, int Q[3001][3001], int x){
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			ps[i + 1][j + 1] = ps[i + 1][j] + ps[i][j + 1] - ps[i][j] + (Q[i][j] <= x);
		}
	}
	for(int i = 0; i <= R - H; i++){
		for(int j = 0; j <= C - W; j++){
			if(sum(i, i + H - 1, j, j + W - 1) >= (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;
	while(lo != hi){
		int mid = (lo + hi) / 2;
		if(ok(R, C, H, W, Q, mid)){
			hi = mid;
		}else{
			lo = mid + 1;
		}
	}
	return lo;
}

Subtask #1

20.0 / 20.0

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

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	560 KB	Output is correct
4	Correct	2 ms	1236 KB	Output is correct
5	Correct	2 ms	1108 KB	Output is correct
6	Correct	1 ms	1236 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	560 KB	Output is correct
4	Correct	2 ms	1236 KB	Output is correct
5	Correct	2 ms	1108 KB	Output is correct
6	Correct	1 ms	1236 KB	Output is correct
7	Correct	9 ms	3924 KB	Output is correct
8	Correct	9 ms	3892 KB	Output is correct
9	Correct	9 ms	3840 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	560 KB	Output is correct
4	Correct	2 ms	1236 KB	Output is correct
5	Correct	2 ms	1108 KB	Output is correct
6	Correct	1 ms	1236 KB	Output is correct
7	Correct	9 ms	3924 KB	Output is correct
8	Correct	9 ms	3892 KB	Output is correct
9	Correct	9 ms	3840 KB	Output is correct
10	Correct	103 ms	22848 KB	Output is correct
11	Correct	101 ms	22784 KB	Output is correct
12	Correct	54 ms	15400 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	560 KB	Output is correct
4	Correct	2 ms	1236 KB	Output is correct
5	Correct	2 ms	1108 KB	Output is correct
6	Correct	1 ms	1236 KB	Output is correct
7	Correct	9 ms	3924 KB	Output is correct
8	Correct	9 ms	3892 KB	Output is correct
9	Correct	9 ms	3840 KB	Output is correct
10	Correct	103 ms	22848 KB	Output is correct
11	Correct	101 ms	22784 KB	Output is correct
12	Correct	54 ms	15400 KB	Output is correct
13	Correct	1054 ms	140164 KB	Output is correct
14	Correct	990 ms	140016 KB	Output is correct
15	Correct	912 ms	132980 KB	Output is correct