| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1296262 | mihajlo0404 | Quality Of Living (IOI10_quality) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inf = 2000000000000;
int rectangle(int r, int c, int h, int w, vector<vector<int>> q) {
int l1 = 1, r1 = r*c, dodajemo;
while (l1 < r1) {
ll m = (l1 + r1)/2;
vector<vector<int>>vece(r, vector<int>(c, 0));
bool moze = false;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (q[i][j] <= m) {
dodajemo = 1;
}
else {
dodajemo = -1;
}
if (i == 0 and j == 0) {
vece[i][j] = dodajemo;
}
else if (i == 0) {
vece[i][j] = vece[i][j - 1] + dodajemo;
}
else if (j == 0) {
vece[i][j] = vece[i - 1][j] + dodajemo;
}
else {
vece[i][j] = vece[i - 1][j] + vece[i][j - 1] - vece[i - 1][j - 1] + dodajemo;
}
if (i + 1 >= h and j + 1 >= w) {
int ima = vece[i][j];
if (i >= h) {
ima -= vece[i - h][j];
}
if (j >= w) {
ima -= vece[i][j - w];
}
if (i >= h and j >= w) {
ima += vece[i - h][j - w];
}
if (ima > 0) {
moze = true;
}
}
}
}
if (moze) {
r1 = m;
}
else {
l1 = m + 1;
}
}
return l1;
}