Advertisement
erek1e

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

Jun 27th, 2022
1,170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement