Advertisement
erek1e

IOI '05 P1 - Garden

Jul 4th, 2022
846
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int INF = 1e9;
  8.  
  9. int main() {
  10.     int l, w, n, k;
  11.     cin >> l >> w >> n >> k;
  12.     vector<vector<int>> grid(1+l, vector<int>(1+w));
  13.     for (int i = 0; i < n; ++i) {
  14.         int a, b; cin >> a >> b;
  15.         ++grid[a][b];
  16.     }
  17.     for (int i = 1; i <= l; ++i) {
  18.         for (int j = 1; j <= w; ++j) {
  19.             grid[i][j] += grid[i-1][j] + grid[i][j-1] - grid[i-1][j-1];
  20.         }
  21.     }
  22.     auto getSum = [&grid](int left, int right, int top, int bottom) { // rectangle sum
  23.         return grid[bottom][right] - grid[bottom][left-1] - grid[top-1][right] + grid[top-1][left-1];
  24.     };
  25.    
  26.     vector<int> leftOf(1+w, INF), rightOf(1+w, INF), above(1+l, INF), below(1+l, INF);
  27.     for (int left = 1; left <= w; ++left) {
  28.         for (int right = left; right <= w; ++right) {
  29.             for (int top = 1, bottom = 0; top <= l; ++top) { // sliding window
  30.                 while (bottom < l && getSum(left, right, top, bottom) < k) ++bottom;
  31.                 if (getSum(left, right, top, bottom) == k) {
  32.                     int p = 2*(right-left+1 + bottom-top+1);
  33.                     leftOf[right] = min(leftOf[right], p);
  34.                     rightOf[left] = min(rightOf[left], p);
  35.                     above[bottom] = min(above[bottom], p);
  36.                     below[top] = min(below[top], p);
  37.                 }
  38.             }
  39.         }
  40.     }
  41.  
  42.     int minPerimeterSum = INF;
  43.     for (int i = 1; i < w; ++i) {
  44.         leftOf[i] = min(leftOf[i], leftOf[i-1]);
  45.         minPerimeterSum = min(minPerimeterSum, leftOf[i]+rightOf[i+1]);
  46.     }
  47.     for (int i = 1; i < l; ++i) {
  48.         above[i] = min(above[i], above[i-1]);
  49.         minPerimeterSum = min(minPerimeterSum, above[i]+below[i+1]);
  50.     }
  51.     if (minPerimeterSum >= INF) cout << "NO" << endl;
  52.     else cout << minPerimeterSum << endl;
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement