IOI '10 P3 - Quality of Living (Standard I/O)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int r, c, h, w;
    cin >> r >> c >> h >> w;
    vector<vector<int>> q(r, vector<int>(c));
    for (vector<int> &row : q) {
        for (int &cell : row) cin >> cell;
    }

    // Binary search on answer
    int left = 0, right = r*c;
    while (right-left > 1) {
        int mid = (left + right) / 2;
        // check if there is a rectangle with median <= mid

        vector<vector<int>> big(1+r, vector<int>(1+c)); // number bigger than mid in "prefix rectangle"
        for (int i = 1; i <= r; ++i) {
            for (int j = 1; j <= c; ++j) big[i][j] = big[i-1][j] + big[i][j-1] - big[i-1][j-1] + (q[i-1][j-1] > mid);
        }
        auto bigInRectangle = [&big](int r0, int c0, int r1, int c1) {
            return big[r1][c1] - big[r0-1][c1] - big[r1][c0-1] + big[r0-1][c0-1];
        };
        bool found = false;
        for (int i = 1; i+h-1 <= r && !found; ++i) {
            for (int j = 1; j+w-1 <= c && !found; ++j) {
                found = 2*bigInRectangle(i, j, i+h-1, j+w-1) < h*w;
            }
        }
        if (found) right = mid;
        else left = mid;
    }
    cout << right << endl;
    return 0;
}