# IOI '05 P1 - Garden

Jul 4th, 2022
949
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }