oj.uz

답안 #404469

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404469 2021-05-14T13:02:59 Z Drew_ 삶의 질 (IOI10_quality) C++17
100 / 100
 2624 ms 89936 KB 
#include "quality.h"
#include <functional>
using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {

	int pfx[3001][3001];
	function<bool(int)> check = [&](int x)
	{
		for (int i = 1; i <= R; ++i)
		{
			for (int j = 1; j <= C; ++j)
			{
				if (Q[i-1][j-1] > x) pfx[i][j] = -1;
				else pfx[i][j] = 1; 

				pfx[i][j] += pfx[i-1][j] + pfx[i][j-1] - pfx[i-1][j-1];
			}
		}

		int mx = -1e9;
		for (int i = 1; i <= R-H+1; ++i)
		{
			for (int j = 1; j <= C-W+1; ++j)
			{
				//sum from (i, j) to (i+H-1, j+W-1)
				mx = max(mx, pfx[i+H-1][j+W-1] - pfx[i+H-1][j-1] - pfx[i-1][j+W-1] + pfx[i-1][j-1]);
			}
		}
		return mx >= 0;
	};

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

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 35532 KB Output is correct
2 Correct 16 ms 35572 KB Output is correct
3 Correct 15 ms 35532 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 35532 KB Output is correct
2 Correct 16 ms 35572 KB Output is correct
3 Correct 15 ms 35532 KB Output is correct
4 Correct 17 ms 35992 KB Output is correct
5 Correct 20 ms 35916 KB Output is correct
6 Correct 18 ms 36020 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 35532 KB Output is correct
2 Correct 16 ms 35572 KB Output is correct
3 Correct 15 ms 35532 KB Output is correct
4 Correct 17 ms 35992 KB Output is correct
5 Correct 20 ms 35916 KB Output is correct
6 Correct 18 ms 36020 KB Output is correct
7 Correct 36 ms 37536 KB Output is correct
8 Correct 37 ms 37592 KB Output is correct
9 Correct 35 ms 37452 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 35532 KB Output is correct
2 Correct 16 ms 35572 KB Output is correct
3 Correct 15 ms 35532 KB Output is correct
4 Correct 17 ms 35992 KB Output is correct
5 Correct 20 ms 35916 KB Output is correct
6 Correct 18 ms 36020 KB Output is correct
7 Correct 36 ms 37536 KB Output is correct
8 Correct 37 ms 37592 KB Output is correct
9 Correct 35 ms 37452 KB Output is correct
10 Correct 285 ms 50160 KB Output is correct
11 Correct 278 ms 50160 KB Output is correct
12 Correct 148 ms 44868 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 35532 KB Output is correct
2 Correct 16 ms 35572 KB Output is correct
3 Correct 15 ms 35532 KB Output is correct
4 Correct 17 ms 35992 KB Output is correct
5 Correct 20 ms 35916 KB Output is correct
6 Correct 18 ms 36020 KB Output is correct
7 Correct 36 ms 37536 KB Output is correct
8 Correct 37 ms 37592 KB Output is correct
9 Correct 35 ms 37452 KB Output is correct
10 Correct 285 ms 50160 KB Output is correct
11 Correct 278 ms 50160 KB Output is correct
12 Correct 148 ms 44868 KB Output is correct
13 Correct 2582 ms 74760 KB Output is correct
14 Correct 2624 ms 74716 KB Output is correct
15 Correct 2408 ms 89936 KB Output is correct