oj.uz

Submission #758615

# Submission time Handle Problem Language Result Execution time Memory
758615 2023-06-15T01:25:39 Z SanguineChameleon Quality Of Living (IOI10_quality) C++17
100 / 100
 1893 ms 140388 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;

int n, m, h, w;
int (*a)[3001];
int pref[3020][3020];

int get(int lx, int ly, int rx, int ry) {
	return pref[rx][ry] - pref[rx][ly - 1] - pref[lx - 1][ry] + pref[lx - 1][ly - 1];
}

bool check(int x) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			pref[i + 1][j + 1] = (a[i][j] <= x ? 1 : -1);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			pref[i][j] += pref[i][j - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			pref[i][j] += pref[i - 1][j];
		}
	}
	for (int i = h; i <= n; i++) {
		for (int j = w; j <= m; j++) {
			if (get(i - h + 1, j - w + 1, i, j) > 0) {
				return true;
			}
		}
	}
	return false;
}

int rectangle(int _n, int _m, int _h, int _w, int _a[3001][3001]) {
	n = _n;
	m = _m;
	h = _h;
	w = _w;
	a = _a;
	int res = -1;
	int lt = 1;
	int rt = n * m;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		if (check(mt)) {
			res = mt;
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	return res;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 568 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 568 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1156 KB Output is correct
6 Correct 2 ms 1224 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 568 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1156 KB Output is correct
6 Correct 2 ms 1224 KB Output is correct
7 Correct 14 ms 3820 KB Output is correct
8 Correct 16 ms 3924 KB Output is correct
9 Correct 14 ms 3796 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 568 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1156 KB Output is correct
6 Correct 2 ms 1224 KB Output is correct
7 Correct 14 ms 3820 KB Output is correct
8 Correct 16 ms 3924 KB Output is correct
9 Correct 14 ms 3796 KB Output is correct
10 Correct 188 ms 22892 KB Output is correct
11 Correct 176 ms 22892 KB Output is correct
12 Correct 97 ms 15432 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 568 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1156 KB Output is correct
6 Correct 2 ms 1224 KB Output is correct
7 Correct 14 ms 3820 KB Output is correct
8 Correct 16 ms 3924 KB Output is correct
9 Correct 14 ms 3796 KB Output is correct
10 Correct 188 ms 22892 KB Output is correct
11 Correct 176 ms 22892 KB Output is correct
12 Correct 97 ms 15432 KB Output is correct
13 Correct 1739 ms 140376 KB Output is correct
14 Correct 1893 ms 140388 KB Output is correct
15 Correct 1688 ms 133416 KB Output is correct