Submission #481487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
481487	2021-10-21T03:09:31 Z	Qkake	Quality Of Living (IOI10_quality)	C++17	100 / 100	1639 ms	140148 KB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MX = 3001;
 
bool ok(int level, int R, int C, int r, int c, int Q[MX][MX]) {
	int sum[MX][MX];
	for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) 
      	sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + (Q[i - 1][j - 1] > level ? -1 : 1);
	for (int i = 1; i + r - 1 <= R; i++) for (int j = 1; j + c - 1 <= C; j++) 
		if (sum[i + r - 1][j + c - 1] - sum[i - 1][j + c - 1] - sum[i + r - 1][j - 1] + sum[i - 1][j - 1] > 0) return true;
	return false;
}
 
int rectangle(int R, int C, int H, int W, int Q[MX][MX]) {
	int lo = 1, hi = R * C, res = 1;
	while (lo <= hi) {
		int mid = lo + (hi - lo) / 2;
		if (ok(mid, R, C, H, W, Q)) { res = mid; hi = mid - 1; } 
      	else lo = mid + 1;
	}
	return res;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	35532 KB	Output is correct
2	Correct	19 ms	35636 KB	Output is correct
3	Correct	17 ms	35660 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	35532 KB	Output is correct
2	Correct	19 ms	35636 KB	Output is correct
3	Correct	17 ms	35660 KB	Output is correct
4	Correct	18 ms	35916 KB	Output is correct
5	Correct	18 ms	36024 KB	Output is correct
6	Correct	19 ms	36000 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	35532 KB	Output is correct
2	Correct	19 ms	35636 KB	Output is correct
3	Correct	17 ms	35660 KB	Output is correct
4	Correct	18 ms	35916 KB	Output is correct
5	Correct	18 ms	36024 KB	Output is correct
6	Correct	19 ms	36000 KB	Output is correct
7	Correct	31 ms	37552 KB	Output is correct
8	Correct	31 ms	37496 KB	Output is correct
9	Correct	29 ms	37488 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	35532 KB	Output is correct
2	Correct	19 ms	35636 KB	Output is correct
3	Correct	17 ms	35660 KB	Output is correct
4	Correct	18 ms	35916 KB	Output is correct
5	Correct	18 ms	36024 KB	Output is correct
6	Correct	19 ms	36000 KB	Output is correct
7	Correct	31 ms	37552 KB	Output is correct
8	Correct	31 ms	37496 KB	Output is correct
9	Correct	29 ms	37488 KB	Output is correct
10	Correct	191 ms	50160 KB	Output is correct
11	Correct	182 ms	50140 KB	Output is correct
12	Correct	99 ms	44688 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	35532 KB	Output is correct
2	Correct	19 ms	35636 KB	Output is correct
3	Correct	17 ms	35660 KB	Output is correct
4	Correct	18 ms	35916 KB	Output is correct
5	Correct	18 ms	36024 KB	Output is correct
6	Correct	19 ms	36000 KB	Output is correct
7	Correct	31 ms	37552 KB	Output is correct
8	Correct	31 ms	37496 KB	Output is correct
9	Correct	29 ms	37488 KB	Output is correct
10	Correct	191 ms	50160 KB	Output is correct
11	Correct	182 ms	50140 KB	Output is correct
12	Correct	99 ms	44688 KB	Output is correct
13	Correct	1639 ms	140148 KB	Output is correct
14	Correct	1604 ms	140140 KB	Output is correct
15	Correct	1446 ms	133260 KB	Output is correct