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

Jun 27th, 2022
1,317
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3.
4. using namespace std;
5.
6. int main() {
7.     int r, c, h, w;
8.     cin >> r >> c >> h >> w;
9.     vector<vector<int>> q(r, vector<int>(c));
10.     for (vector<int> &row : q) {
11.         for (int &cell : row) cin >> cell;
12.     }
13.
14.     // Binary search on answer
15.     int left = 0, right = r*c;
16.     while (right-left > 1) {
17.         int mid = (left + right) / 2;
18.         // check if there is a rectangle with median <= mid
19.
20.         vector<vector<int>> big(1+r, vector<int>(1+c)); // number bigger than mid in "prefix rectangle"
21.         for (int i = 1; i <= r; ++i) {
22.             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);
23.         }
24.         auto bigInRectangle = [&big](int r0, int c0, int r1, int c1) {
25.             return big[r1][c1] - big[r0-1][c1] - big[r1][c0-1] + big[r0-1][c0-1];
26.         };
27.         bool found = false;
28.         for (int i = 1; i+h-1 <= r && !found; ++i) {
29.             for (int j = 1; j+w-1 <= c && !found; ++j) {
30.                 found = 2*bigInRectangle(i, j, i+h-1, j+w-1) < h*w;
31.             }
32.         }
33.         if (found) right = mid;
34.         else left = mid;
35.     }
36.     cout << right << endl;
37.     return 0;
38. }