oj.uz

Submission #550987

# Submission time Handle Problem Language Result Execution time Memory
550987 2022-04-19T16:02:21 Z Jomnoi Quality Of Living (IOI10_quality) C++17
100 / 100
 2543 ms 140408 KB 
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;

bool solve(int mid, int R, int C, int H, int W, int a[3001][3001]) {
	vector <vector <int>> qs(3001, vector <int> (3001, 0));
	for(int i = 1; i <= R; i++) {
		for(int j = 1; j <= C; j++) {
			qs[i][j] += qs[i - 1][j] + qs[i][j - 1] - qs[i - 1][j - 1];
			if(a[i - 1][j - 1] < mid) {
				qs[i][j]--;
			}
			else if(a[i - 1][j - 1] > mid) {
				qs[i][j]++;
			}
		}
	}

	for(int i = H; i <= R; i++) {
		for(int j = W; j <= C; j++) {
			if(qs[i][j] - qs[i - H][j] - qs[i][j - W] + qs[i - H][j - W] <= 0) {
				return true;
			}
		}
	}
	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 1, r = R * C;
	while(l < r) {
		int mid = (l + r) / 2;

		if(solve(mid, R, C, H, W, Q) == true) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	return l;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 36024 KB Output is correct
2 Correct 146 ms 35904 KB Output is correct
3 Correct 137 ms 35824 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 36024 KB Output is correct
2 Correct 146 ms 35904 KB Output is correct
3 Correct 137 ms 35824 KB Output is correct
4 Correct 205 ms 36360 KB Output is correct
5 Correct 199 ms 36236 KB Output is correct
6 Correct 183 ms 36200 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 36024 KB Output is correct
2 Correct 146 ms 35904 KB Output is correct
3 Correct 137 ms 35824 KB Output is correct
4 Correct 205 ms 36360 KB Output is correct
5 Correct 199 ms 36236 KB Output is correct
6 Correct 183 ms 36200 KB Output is correct
7 Correct 253 ms 37872 KB Output is correct
8 Correct 256 ms 37872 KB Output is correct
9 Correct 262 ms 37784 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 36024 KB Output is correct
2 Correct 146 ms 35904 KB Output is correct
3 Correct 137 ms 35824 KB Output is correct
4 Correct 205 ms 36360 KB Output is correct
5 Correct 199 ms 36236 KB Output is correct
6 Correct 183 ms 36200 KB Output is correct
7 Correct 253 ms 37872 KB Output is correct
8 Correct 256 ms 37872 KB Output is correct
9 Correct 262 ms 37784 KB Output is correct
10 Correct 508 ms 50376 KB Output is correct
11 Correct 523 ms 50456 KB Output is correct
12 Correct 403 ms 45012 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 36024 KB Output is correct
2 Correct 146 ms 35904 KB Output is correct
3 Correct 137 ms 35824 KB Output is correct
4 Correct 205 ms 36360 KB Output is correct
5 Correct 199 ms 36236 KB Output is correct
6 Correct 183 ms 36200 KB Output is correct
7 Correct 253 ms 37872 KB Output is correct
8 Correct 256 ms 37872 KB Output is correct
9 Correct 262 ms 37784 KB Output is correct
10 Correct 508 ms 50376 KB Output is correct
11 Correct 523 ms 50456 KB Output is correct
12 Correct 403 ms 45012 KB Output is correct
13 Correct 2534 ms 140408 KB Output is correct
14 Correct 2543 ms 140404 KB Output is correct
15 Correct 2292 ms 133400 KB Output is correct