oj.uz

Submission #512673

# Submission time Handle Problem Language Result Execution time Memory
512673 2022-01-16T16:18:14 Z saral Quality Of Living (IOI10_quality) C++14
100 / 100
 1855 ms 106256 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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