# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1091523 | dylanliang | Quality Of Living (IOI10_quality) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
using namespace std;
bool medianExists(int const& mid, vector<vector<int>> grid, int const& r, int const& c, int const& h, int const& w) {
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
if (mid > grid[i][j]) {
grid[i][j] = -1;
} else if (mid < grid[i][j]) {
grid[i][j] = 1;
} else {
grid[i][j] = 0;
}
}
}
int count = 0;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
count += grid[i][j];
}
}
if (count <= 0) return true;
bool movingRight = true;
for (int i = 0; i < r-h; ++i) {
if (movingRight) {
for (int j = 0; j < c-w; ++j) {
for (int k = i; k < i+h; ++k) {
count += grid[k][j+w] - grid[k][j];
}
}
if (count <= 0) return true;
for (int j = c-w-1; j < c; ++j) {
count += grid[i+h][j] - grid[i][j];
}
if (count <= 0) return true;
} else {
for (int j = c-w-1; j >= 0; --j) {
for (int k = i; k < i+h; ++k) {
count += grid[k][j] - grid[k][j+w];
}
}
if (count <= 0) return true;
for (int j = 0; j < w; ++j) {
count += grid[i+h][j] - grid[i][j];
}
if (count <= 0) return true;
}
movingRight = not movingRight;
}
return false;
}
int main() {
int r, c, h, w;
cin >> r >> c >> h >> w;
vector<vector<int>> grid(r, vector<int>(c, 0));
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
cin >> grid[i][j];
}
}
int lo = 1;
int hi = r*c;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (medianExists(mid, grid, r, c, h, w)) {
hi = mid;
} else {
lo = mid+1;
}
}
cout << (lo+hi) / 2;
return 0;
}